레이팅 미적용설명
소문자 알파벳 문자열 \(S\)가 주어진다. 어떤 문자열이 앞에서 읽으나 뒤에서 읽으나 같으면 회문(palindrome)이라 한다.
\(S\)의 서로 다른 회문 부분 문자열 중에서, \(S\) 안에 \(K\)번 이상 등장하는 것의 개수를 구하여라. 한 회문이 서로 다른 시작 위치에서 여러 번 등장하면 그 횟수만큼 센다.
예를 들어 \(S=\texttt{aba}\)에서 회문 \(\texttt{a}\)는 위치 \(1\)과 \(3\)에서 두 번 등장한다.
제약
\(1 \le K \le |S|\)
\(1 \le |S| \le 300{,}000\)
\(S\)는 소문자 알파벳 a~z로만 이루어져 있다.
입력 형식
첫 줄에 정수 \(K\)가 주어진다.
둘째 줄에 문자열 \(S\)가 주어진다.
출력 형식
\(S\) 안에 \(K\)번 이상 등장하는 서로 다른 회문 부분 문자열의 개수를 출력한다.
예제 1
입력
2
abacaba
출력
3설명
회문과 등장 횟수: a(4), b(2), c(1), aba(2), aca(1), bacab(1), abacaba(1) 등. 2번 이상 등장하는 회문은 a, b, aba로 3개이다.
예제 2
입력
2
aaaa
출력
3설명
회문 a(4), aa(3), aaa(2), aaaa(1). 2번 이상 등장하는 것은 a, aa, aaa로 3개이다.
문제 정보
riseoj 작성
출처 Original
태그