[BOJ 1701] Cubeditor (백준, JAVA, KMP)

www.acmicpc.net/problem/1701

1701번: Cubeditor

 

## KMP 알고리즘

---

찾아야 하는 단어의 길이를 S, 전체 문서의 길이를 T라고 해보자. 모든 문서에서 단어를 비교하게 된다면 최악의 시간 복잡도는 O(T * S)가 된다.

 

 

O(T * S)보다 시간을 줄일 수 있는 방법을 KMP 알고리즘이라고 한다. KMP 알고리즘의 핵심은, 검사된 문자의 정보를 이용하는 것이다.

 

 

찾아야 하는 단어의 문자의 substring(0, n)마다 접두사와 접미사가 동일한 최장 길이를 구해놓는 것이 핵심이다. 

 

 

## 문제 해결

---

이 문제는 KMP 알고리즘을 모른다면 풀 수가 없으므로, KMP 알고리즘에 대한 이해가 핵심이다. 

 

 

 

KMP의 알고리즘에서 접두사와 접미사의 최장 길이를 구하는 부분을 이용하면 된다.

 

 

## 해설코드

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] pi;
    static String s;
    static int answer = 0;
    
    public static void main (String[] args) throws java.lang.Exception
    {
        s = br.readLine();
        
        for(int i = 0; i < s.length(); i++){
            int matches = 0;
            String str = s.substring(i, s.length());
            
            pi = new int[str.length()];
            
            for(int j = 1; j < str.length(); j++){
                while(matches > 0 && str.charAt(matches) != str.charAt(j)){
                    matches = pi[matches - 1];
                }
                    
                if(str.charAt(matches) == str.charAt(j)){
                    matches += 1;
                }
                
                pi[j] = matches;
                answer = Math.max(answer, pi[j]);
            }
        }
        
        
        System.out.println(answer);
    }
}