[BOJ] 백준 1605번 반복 부분 문자열 (Java)

#1605 반복 부분문자열

난이도 : 플레 3

유형 : 접미사 배열, LCP 배열

1605번: 반복 부분문자열

(3033번 중복 문제)

3033번: 가장 긴 문자열

▸ 문제

알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'이라고 부르자.

문자열이 주어지면, 가장 긴 '반복 부분문자열'의 길이를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 문자열의 길이 L(1 ≤ L ≤ 200,000)이 주어진다. 둘째 줄에는 문자열을 이루는 L개의 알파벳 소문자들이 띄어쓰기 없이 주어진다.

▸ 출력

첫째 줄에 가장 긴 '반복 부분문자열'의 길이를 출력한다. 만일 '반복 부분문자열'이 하나도 존재하지 않는다면 0을 출력한다.

 

문제 풀이  

 반복 부분문자열은 주어진 문자열의 부분문자열 중 두 개 이상 존재하는 문자열 말한다. naive하게 접근하면 부분문자열을 직접 다 구하면 \(n\times(n+1)\over2\) 이 된다. 그리고 이를 일일이 다 비교하면 반복 부분문자열의 최대 길이를 구할 수 있다. 그런데 최대 문자열의 길이 L은 20만으로 모든 부분문자열(약 200억)을 다 비교하기 위해서는 이중포문을 돌려야 하는데 말이 안된다.

 

이를 접미사 배열과 lcp 배열의 개념으로 해당 문제를 풀이할 수 있다. 만약 반복 부분문자열이 두 개 이상 존재한다면 공통된 해당 부분문자열을 접두사로 가지는 접미사는 사전순으로 인접해 있을 것이다. 이를 역으로 생각하면 사전순으로 정렬한 접미사 배열이 있으면 이를 이용하여 구해진 최장 공통 접두사 LCP 중 가장 큰 값이 반복 부분문자열의 최대 길이임을 알 수 있게 된다.

 

예제로 주어진 "tellmetellmetetetetetetellme"로 구해보면 다음과 같다.

• 반복 부분문자열의 최대길이 = LCP 최댓값
• etetetetetellme (14 ~ 28) 15
• etetetetetetellme (12 ~ 28) 17

idx	i (접미사 시작 위치)	sa[i...]	lcp
0	27	e	1
1	23	ellme	5
2	1	ellmetellmetetetetetetellme	7
3	7	ellmetetetetetetellme	1
4	21	etellme	7
5	5	etellmetetetetetetellme	3
6	19	etetellme	5
7	17	etetetellme	7
8	15	etetetetellme	9
9	13	etetetetetellme	11
10	11	etetetetetetellme	0
...	...	....	...
26	14	tetetetetellme	8
27	12	tetetetetetellme	10

 

접미사 배열을 만드는 데 걸리는 시간은 \(O(n\times(\log n)^2)\)이 걸리고 LCP 배열을 만드는 시간은 Kasai 알고리즘을 사용하면 \(O(n)\)에 가능하다.

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static int n;
	static class CompUsingT implements Comparator<Integer> {
		int t;
		int[] group;

		public CompUsingT(int t, int[] group) {
			this.t = t;
			this.group = group;
		}

		public void changeValues(int t, int[] group) {
			this.t = t;
			this.group = group;
		}

		@Override
		public int compare(Integer o1, Integer o2) {
			if (group[o1] != group[o2]) {
				return group[o1] - group[o2];
			}

			int left = o1 + t, right = o2 + t;
			if (left > n) {
				left = n;
			}

			if (right > n) {
				right = n;
			}
			return group[left] - group[right];
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		String text = br.readLine();
		List<Integer> sa = getSuffixArray(text);
		int max = getLongestSubStrLen(text, sa);
		System.out.println(max);
	}

	static List<Integer> getSuffixArray(String text) {
		int t = 1;

		List<Integer> sa = new ArrayList<>();
		int[] group = new int[n + 1];
		for (int i = 0; i < n; i++) {
			sa.add(i);
			group[i] = text.charAt(i) - 'a';
		}
		group[n] = -1;

		CompUsingT comp = new CompUsingT(t, group);
		while (t < n) {
			Collections.sort(sa, comp);

			t *= 2;
			if (t >= n)
				break;

			int[] nGroup = new int[n + 1];
            nGroup[n] = -1;
			for (int i = 1; i < n; i++) {
				if (comp.compare(sa.get(i - 1), sa.get(i)) < 0) {
					nGroup[sa.get(i)] = nGroup[sa.get(i - 1)] + 1;
				} else {
					nGroup[sa.get(i)] = nGroup[sa.get(i - 1)];
				}
			}
			group = nGroup;
			comp.changeValues(t, group);
		}
		return sa;
	}

	static int getLongestSubStrLen(String text, List<Integer> sa) {
		int[] lcp = new int[n - 1];
		int[] isa = new int[n];
		for (int i = 0; i < n; i++) {
			isa[sa.get(i)] = i;
		}
			
		int max = 0;
		int h = 0;
		for (int i = 0; i < n; i++) {
			int k = isa[i];
			if (k == n - 1) continue;

			int j = sa.get(k + 1);
			while (i + h < n && j + h < n) {
				if (text.charAt(i + h) != text.charAt(j + h)) break;

				h++;
			}
			lcp[k] = h;
			max = Math.max(max, h);
			if (h > 0) {
				h -= 1;
			}
		}	
		return max;
	}
}

 

​