[BOJ] 백준 13506번 카멜레온 부분 문자열 (Java)

#13506 카멜레온 부분 문자열

난이도 : 플레 4

유형 : 문자열 / kmp

13506번: 카멜레온 부분 문자열

▸ 문제

문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.

문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.

예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.

▸ 입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 10^6을 넘지 않는 자연수이다.

▸ 출력

가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T가 존재하지 않으면 -1을 출력한다.

 

문제 풀이  

카멜레온 부분문자열은 접두사와 접미사가 될 수 있으면서 접두사, 접미사 사이에도 존재하는 문자열을 뜻한다. 이를 구하기 위해 KMP 알고리즘의 부분 일치테이블(pi)을 사용했다.

• pi[i] = pattern(0...i)의 접두사도 되고 접미사도 되는 문자열의 최대 길이

 

해당 테이블을 구하면 접두사와 접미사가 될 수 있는 최대 길이 문자열은 쉽게 구할 수 있다. 여기서 그 사이에 위치하는 문자열이 존재하는지만 체크해주면 된다. 이를 위해서는 아호코라식 알고리즘에서 사용하는 실패 링크에 대한 개념을 이용해야 한다. 

• failure(s) = s 의 접미사이면서 가장 긴 문자열까지 가는 화살표
• 실패 링크를 이용하여 접미사에 포함되면서(= 접두사에도 포함) 해당 부분문자열 중 가장 긴 접미사부터 순차대로 재귀 탐색해주면 된다. 

 

문자열 "papapapap"에 대해서 실패 링크를 구해보면 다음과 같다. 이는 전체적인 그래프이고 실제로는 pi[len-1] = 5에서 탐색이 종료된다. 

탐색 과정은 다음과 같이 이루어진다.

1. len = pi[n-1] = 7: 접두사이면서 접미사인 가장 긴 문자열의 길이는 7이므로 해당 노드 "papapap"로 이동
2. (1~n-2) 접두사, 접미사를 제외한 pi 테이블에 또 하나의 7이 있는지 탐색한다.
3. len = pi[len-1] = 5: 7이 없으므로, 그 다음으로 현재 노드의 접미사중 가장 긴 노드 "papap"로 이동
4. (1~n-2) 접두사, 접미사를 제외한 pi 테이블에 5가 있으므로 탐색을 종료한다.

 

풀이 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String text = br.readLine();
		int n = text.length();
		
		int idx = 0;
		int[] pi = new int[n];
		for(int i=1; i<n; i++) {
			while(idx > 0 && text.charAt(i) != text.charAt(idx)) {
				idx = pi[idx-1];
			}
			if(text.charAt(i) == text.charAt(idx)) {
				pi[i] = ++idx;
			}
		}
		
		String pattern = "";
		int len = pi[n-1];
		out: while(len > 0) {
			for(int i=1; i<n-1; i++) {
				if(pi[i] == len) {
					pattern = text.substring(i-len+1, i+1);
					break out;
				}
			}
			len = pi[len-1];
		}
		
		if(pattern.isEmpty()) {
			System.out.println("-1");
			return;
		}
	
		System.out.println(pattern);
	}
}