[BOJ] 1701. Cubeditor

KMP를 활용하는 문자열 문제이다.

이 문제를 맨처음엔 모든 문자열 패턴을 구해서 입력문자열에서 패턴을 찾는 방식으로 생각해보았다. 하지만 문자열 최대 길이가 5000이기에 모든 패턴을 구하는건 불가능했다. 그래서 생각해보니 KMP를 사용할때 접두사와 접미사를 이용하여 패턴의 길이를 구하는 pi를 활용하는 방안을 떠올렸다. 이것을 이용하면 2번이상 등자하며 최장길이를 구할 수 있게 되기에 적용해보았다. 단, abbcbba와 같은 패턴에서는 bb를 못찾기에 이것을 위해선 bbcbba를 확인해야하는 반례가 생긴다. 그래서 입력문자열의 앞에서부터 하나씩 줄여주며 pi를 구하는 방식으로 풀어보았다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_1701_Cubeditor {
    static String input;
    static int len;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        input = br.readLine();
        len = input.length();
 
        int answer = 0;
        for (int i = 0; i < len; i++) {
 
            answer = Math.max(answer, getPi(input.substring(i, len)));
        }
 
        System.out.println(answer);
    }
 
    static int getPi(String str) {
        int strLen = str.length();
        int[] pi = new int[strLen];
        int j = 0;
 
        int max = 0;
        for (int i = 1; i < strLen; i++) {
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = pi[j - 1];
            }
            if (str.charAt(i) == str.charAt(j)) {
                pi[i] = ++j;
                max = Math.max(max, pi[i]);
            }
        }
 
        return max;
    }
}