문자열 안에서 적어도 한 번 이상 반복되는 부분문자열(즉, 전체 문자열에서 두 번 이상 등장하는 부분문자열)의 최대 길이를 구하는 문제이다. 길이 \(L\) 은 최대 200,000이므로, 단순한 모든 구간 비교는 시간 내에 불가능하다.
문제 정보
- 시간 제한: 2초
- 메모리 제한: 128MB
- 입력 제한: L ≤ 200,000, 문자열은 소문자
접근 방식
- 가장 긴 반복 부분문자열의 길이는 접미사 배열(Suffix Array)과 LCP 배열(Kasai)로 구할 수 있다.
- 문자열의 모든 접미사를 사전순으로 정렬한 뒤, 인접한 접미사들 간 LCP(최장 공통 접두사)의 최댓값이 정답이 된다.
- 시간 복잡도: 접미사 배열 배가법(O(n log n)) + Kasai O(n) ⇒ O(n log n)
참고로, 이 문제는 해시(이중 롤링 해시) + 이분 탐색(O(n log n))으로도 풀 수 있으나, 본 글에서는 접미사 배열 기반 풀이를 제공한다.
C++ 풀이 (Suffix Array + LCP)
|
|
복잡도
- 시간: O(n log n)
- 공간: O(n)
문제 요약
- 정의: 문자열의 부분문자열 중, 전체 문자열에서 두 번 이상 등장하는 부분문자열을 반복 부분문자열이라 한다. 겹쳐서 등장해도 인정한다.
- 목표: 가장 긴 반복 부분문자열의 길이를 구한다. 없으면 0.
입출력 형식
- 입력
- 첫 줄: 정수 L (1 ≤ L ≤ 200000)
- 둘째 줄: 길이 L의 소문자 문자열 s
- 출력
- 가장 긴 반복 부분문자열의 길이. 없으면 0
예제
입력
|
|
출력
|
|
왜 Suffix Array + LCP로 풀까?
- 모든 접미사를 사전순으로 정렬하면, 반복 부분문자열은 어떤 두 접미사의 공통 접두사로 나타난다.
- 사전순으로 인접한 두 접미사는 공통 접두사 길이가 큰 편이고, 전체 최댓값은 인접한 쌍 중 어딘가에서 반드시 달성된다.
- 따라서, 접미사 배열을 만든 뒤 인접한 접미사들 간 LCP의 최댓값이 곧 정답이다.
증명 스케치: 두 접미사 i, j의 공통 접두사 길이를 x라 하자. 정렬된 접미사 배열에서 i와 j 사이에 있는 접미사들과의 LCP 최소값이 x 이상이므로, 인접한 어느 구간에서 최소 LCP가 x를 달성한다. 그 중 최댓값이 전체 최댓값과 일치한다.
구현 디테일
- 접미사 배열은 배가법(doubling)으로 (rank[i], rank[i+k])를 키로 정렬한다.
- 두 번의 안정적 카운팅 소트로 키2(뒤쪽) → 키1(앞쪽) 순으로 정렬해 O(n) per step을 보장한다.
- 경계를 위해 없는 위치의 랭크는 0으로 치환하기 위해 실제 랭크에 +1 오프셋을 준다.
- 모든 랭크가 서로 달라지면 조기 종료한다.
- LCP는 Kasai 알고리즘으로 O(n) 시간에 계산한다. 직전 LCP에서 1만 감소시키며 재활용한다.
코너 케이스 체크리스트
- L = 1 → 정답 0
- 모든 문자가 서로 다름 → 정답 0
- 모든 문자가 동일(“aaaa…”) → 정답은 L-1
- 겹치는 반복 허용: 예) “aaaa"에서 길이 3의 반복(“aaa”)는 위치 0과 1에서 겹치지만 유효하다
- 입력은 소문자만 가정하므로 알파벳 크기 26, 하지만 구현은 일반 바이트값 기준이라 범용적
참고자료
- Suffix Array — Wikipedia: https://en.wikipedia.org/wiki/Suffix_array
- LCP array — Wikipedia: https://en.wikipedia.org/wiki/LCP_array
- Longest repeated substring problem — Wikipedia: https://en.wikipedia.org/wiki/Longest_repeated_substring_problem
- Suffix Array — cp-algorithms: https://cp-algorithms.com/string/suffix-array.html