반복되는 가장 긴 무늬
플래티넘 I의견: 0
길이 \(N\)의 문자열 \(S\)가 주어진다. \(S\)의 어떤 연속한 부분 문자열이 \(S\) 안에서 서로 다른 시작 위치로 \(K\)번 이상 나타날 때, 이런 부분 문자열 중 가장 긴 것의 길이를 구하여라. 나타나는 구간끼리 겹쳐도 된다.
예를 들어 \(S=\)ababa에서 aba는 위치 \(0\)과 \(2\)에서 두 번 나타난다.
모든 부분 문자열을 일일이 세는 풀이는 통과할 수 없다.
\(1 \le K \le N \le 200{,}000\) (\(N\)은 \(S\)의 길이)
\(S\)는 영문 소문자(a-z)로만 이루어진다.
첫 줄에 정수 \(K\)가 주어진다.
둘째 줄에 소문자 알파벳으로 이루어진 문자열 \(S\)가 주어진다.
조건을 만족하는 가장 긴 부분 문자열의 길이를 출력한다. 그런 부분 문자열이 없으면 \(0\)을 출력한다.
2
ababa
3aba가 위치 0,2에서 두 번 나타나 길이 3이 가능하다. 더 긴 것은 없으므로 답은 3.
2
aabaab
3aab가 위치 0,3에서 두 번 나타나 길이 3. 길이 4 이상은 두 번 나타나지 않으므로 답은 3.
riseoj 작성
출처 Original
평가 및 의견
반복되는 가장 긴 무늬
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
반복되는 가장 긴 무늬