[JAVA] 백준 1701 Cubeditor

https://www.acmicpc.net/problem/1701

1701번: Cubeditor

풀이

n인 어떤 문자열이 주어졌을 때 i = 0 부터 n-1 까지의 경우에 대해  kmp 알고리즘을 적용하고 가장 큰 값을 찾는 문제.

아직까지 kmp 알고리즘이 완벽하게 이해되지 않아서 어려웠다..

 

[참고]

https://devowen.com/310

백준 1701 / Cubeditor / 문자열, KMP / JAVA

https://validming99.tistory.com/162

[JAVA] 백준 1786 찾기

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();

        int answer = 0;
        for(int i=0; i<str.length(); i++){
            String sub = str.substring(i);
            int max = 0;
            int pi[] = new int[sub.length()]; //부분 문자열

            for(int j=1, k=0; j<sub.length();j++){ //j: 접미사 인덱스, k:접두사 인덱스
                while(k>0 && sub.charAt(j) != sub.charAt(k)) k = pi[k-1];
                if(sub.charAt(j) == sub.charAt(k)) max = Math.max(max, pi[j] = ++k);
            }
            
            answer = Math.max(answer, max);
        }
        
        System.out.println(answer);
    }
}