메아리치는 회문
다이아몬드 IV의견: 0
소문자 알파벳 문자열 \(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\)번 이상 등장하는 서로 다른 회문 부분 문자열의 개수를 출력한다.
2
abacaba
3회문과 등장 횟수: a(4), b(2), c(1), aba(2), aca(1), bacab(1), abacaba(1) 등. 2번 이상 등장하는 회문은 a, b, aba로 3개이다.
2
aaaa
3회문 a(4), aa(3), aaa(2), aaaa(1). 2번 이상 등장하는 것은 a, aa, aaa로 3개이다.
riseoj 작성
출처 Original
평가 및 의견
메아리치는 회문
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
메아리치는 회문