문제
문자열 S가 주어질 때, S에서 두 번 이상 등장하는 부분 문자열 중 가장 긴 것의 길이를 구하는 문제이다. 올바른 풀이는 해싱(라빈-카프) 또는 접미사 배열(Suffix Array) + LCP 배열을 사용해야 한다.
입력
첫째 줄에 문자열의 길이 L (1 이상 200,000 이하)이 주어진다. 둘째 줄에 길이 L의 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어진다.
출력
S에서 두 번 이상 등장하는 부분 문자열의 최대 길이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
11 abcababcabc | 5 |
풀이
이 코드는 O(L³)의 브루트포스 완전 탐색으로 구현되어 있어 시간 초과가 발생한다(클래스명에 Fail, 시간초과 명시). 올바른 접근은 이진 탐색 + 라빈-카프 해싱을 조합하는 것이다.
- 모든 시작 인덱스 쌍 (i, j)를 이중 루프로 탐색한다.
- 두 위치에서 시작하는 문자열이 얼마나 일치하는지 한 문자씩 비교한다.
- 최대 일치 길이를 갱신한다.
핵심 아이디어 (올바른 풀이): 이진 탐색으로 정답 길이를 좁혀가며, 길이 k의 부분 문자열이 중복 등장하는지를 라빈-카프 해시로 O(L) 판별한다. 전체 복잡도는 O(L log L). 접미사 배열 + LCP 배열로도 O(L log L)에 해결 가능하다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day27BOJ3033Fail가장긴문자열시간초과 { // 3033 가장 긴 문자열
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int L = Integer.parseInt(br.readLine());
char[] arr = br.readLine().toCharArray();
int cnt = 0;
for (int i = 0; i < L - 1; i++) {
for (int j = i + 1; j < L; j++) {
int tmp = 0;
if (arr[i] == arr[j]) {
tmp++;
int idx = i + 1;
int jdx = j + 1;
while (true) {
if (jdx == L)
break;
if (arr[idx] == arr[jdx])
tmp++;
else
break;
idx++;
jdx++;
}
}
if (tmp > cnt)
cnt = tmp;
}
}
System.out.println(cnt);
br.close();
}
}복잡도
- 시간: O(L³) — 이중 루프 안에서 문자 비교 루프가 추가. 시간 초과 발생
- 공간: O(L) — 문자 배열