레이팅 미적용설명
소문자 알파벳으로 이루어진 문자열 \(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\)번 이상 등장하는 서로 다른 부분 문자열의 개수를 한 줄에 출력한다.
예제 1
입력
2
ababa
출력
5설명
2번 이상 등장하는 부분 문자열: a(3), b(2), ab(2), ba(2), aba(2)로 5개이다. 예를 들어 aba는 위치 1, 3에서 두 번 나온다.
예제 2
입력
3
aaaa
출력
2설명
3번 이상 등장: a는 4번, aa는 3번 등장한다. aaa는 2번, aaaa는 1번이라 제외. 따라서 2개.
문제 정보
riseoj 작성
출처 Original
태그