8072 : 가장 긴 반복 부분 문자열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
하나의 문자열 $S$가 주어집니다.
이 문자열 내에서 두 번 이상 등장하는 부분 문자열 중 가장 긴 것의 길이를 구하는 프로그램을 작성하십시오.
단, 두 부분 문자열이 등장하는 위치는 겹칠 수 있습니다.
[제약 조건]
• $1 \le |S| \le 5{,}000$ (알파벳 소문자)
이 문자열 내에서 두 번 이상 등장하는 부분 문자열 중 가장 긴 것의 길이를 구하는 프로그램을 작성하십시오.
단, 두 부분 문자열이 등장하는 위치는 겹칠 수 있습니다.
[제약 조건]
• $1 \le |S| \le 5{,}000$ (알파벳 소문자)
입력 설명
첫째 줄에 알파벳 소문자로만 구성된 문자열 $S$가 주어집니다. ($1 \le |S| \le 5{,}000$)
출력 설명
두 번 이상 등장하는 부분 문자열 중 가장 긴 것의 길이를 첫째 줄에 출력합니다.
만약 두 번 이상 등장하는 부분 문자열이 존재하지 않으면
만약 두 번 이상 등장하는 부분 문자열이 존재하지 않으면
0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
cabacaba
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
접미사 배열(Suffix Array)을 구한 뒤 인접한 접미사 간의 가장 긴 공통 접두사(LCP, Longest Common Prefix) 배열을 계산하면 LCP 최댓값이 답이 됩니다.
또는 문자열 해싱과 이분 탐색(Binary Search on Length)을 결합하여 $O(N \log^2 N)$에 해결할 수도 있습니다.
또는 문자열 해싱과 이분 탐색(Binary Search on Length)을 결합하여 $O(N \log^2 N)$에 해결할 수도 있습니다.