자주 나오는 부분 문자열
다이아몬드 IV의견: 0
소문자 알파벳으로 이루어진 문자열 \(S\)가 주어진다.
\(S\)의 서로 다른 부분 문자열 중에서, \(S\) 안에 (위치를 달리하여) \(K\)번 이상 등장하는 것의 개수를 구하여라. 같은 내용의 부분 문자열은 한 번만 센다.
예를 들어 \(S=\texttt{ababa}\)에서 부분 문자열 \(\texttt{aba}\)는 위치 \(1\)과 \(3\)에서 두 번 등장한다.
\(|S|\)가 매우 크므로 모든 부분 문자열을 직접 나열할 수 없다.
\(1 \le K \le |S|\)
\(1 \le |S| \le 200{,}000\)
\(S\)는 소문자 알파벳 a~z로만 이루어져 있다.
첫 줄에 정수 \(K\)가 주어진다.
둘째 줄에 문자열 \(S\)가 주어진다.
\(S\) 안에 \(K\)번 이상 등장하는 서로 다른 부분 문자열의 개수를 한 줄에 출력한다.
2
ababa
52번 이상 등장하는 부분 문자열: a(3), b(2), ab(2), ba(2), aba(2)로 5개이다. 예를 들어 aba는 위치 1, 3에서 두 번 나온다.
3
aaaa
23번 이상 등장: a는 4번, aa는 3번 등장한다. aaa는 2번, aaaa는 1번이라 제외. 따라서 2개.
riseoj 작성
출처 Original
평가 및 의견
자주 나오는 부분 문자열
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
자주 나오는 부분 문자열