[BOJ] 백준 1701번 Cubeditor (Java)

#1701 Cubeditor

난이도 : 골드 2

유형 : 문자열 / KMP

1701번: Cubeditor

▸ 문제

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

▸ 입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

▸ 출력

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

 

문제 풀이  

중복되는 부분문자열 중 가장 긴 길이를 구하면 된다. 최대 문자열의 길이가 5000이기 때문에 이중 포문을 써도 25,000,000 정도로 그렇게 오래 걸리지 않는다. 

 

중복 부분 문자열을 구하기 위해서 KMP에서 사용되는 부분 일치 테이블 구하기 로직을 사용할 것이다. n길이 문지열이 있을 때 접두사와 얼마나 일치하는지를 구하는 것이기 때문에 부분문자열 길이를 구하기 아주 간단하다. 

static int[] makeTable(String pattern) {
	int n = pattern.length();
	int[] table = new int[n];
		
	int idx=0;
	for(int i=1; i<n; i++) {
		// 일치하는 문자가 발생했을 때(idx>0), 연속적으로 더 일치하지 않으면 idx = table[idx-1]로 돌려준다.
		while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
			idx = table[idx-1];
		}
			
		if(pattern.charAt(i) == pattern.charAt(idx)) {
			idx += 1;
			table[i] = idx;  
		}
	}
	return table;
}

 

위의 로직에서 반복문 하나만 더 추가해줄 것이다. 왜냐하면 KMP에서는 단순 현재 문자열 접두사에 일치하는 부분 일치 테이블만 구하는데 이번 문제에서 구하고자 하는 것은 접두사와 일치하는 것은 아닌 전체 문자열에서 중복되는 것을 찾는 것이기 떄문이다.

• 예를들어 'aabcdbcdaa'라는 문자열에 대한 답을 구한다면 'bcd'가 가장 긴 부분문자열이다.
• 하지만 위에 있는 로직은 단순 접두사만 기준으로 하기 때문에 'aa'로 인식하게 된다.

 

설계

1. 문자열을 입력받아 부분 일치 테이블을 구한다. makeTable(br.readLine());
   1. 문자열의 길이를 n이라고 할 때, n부터 1까지 접두사 부분을 줄여나가면서 모든 부분 문자열에 대해 탐색한다.
   2. 중복되어 나오는 부분문자열 중에서 가장 긴 길이를 출력한다. max = Math.max(max,idx);

 

풀이 코드 

import java.io.*;

public class Main {
	static int max =0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println(makeTable(br.readLine()));
	}
	
	static int makeTable(String parent) {
		int n = parent.length();
		for(int pos=0; pos<n; pos++) {
			String pattern = parent.substring(pos);
			int n2 = pattern.length();
			int[] table = new int[n2];
			int idx=0;
			for(int i=1; i<n2; i++) {
				while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
					idx = table[idx-1];
				}
				if(pattern.charAt(i) == pattern.charAt(idx)) {
					table[i] = ++idx;
					max = Math.max(max, idx);
				}
			}
		}
		return max;
	}
}