Dot Algo∙ DS/PS

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

루지 2022. 4. 16. 17:05

    #13506 카멜레온 부분 문자열

    난이도 : 플레 4

    유형 : 문자열 / kmp

     

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

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

    www.acmicpc.net

    ▸ 문제

    문자열 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);
    	}
    }