[JAVA] 백준 1701 Cubeditor

valid_ming 2021. 9. 28. 11:34

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

1701번: Cubeditor

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한

www.acmicpc.net

풀이

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

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

[참고]

https://devowen.com/310

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

오늘 살펴볼 문제는 백준 1701 문제이다. https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이..

devowen.com

https://validming99.tistory.com/162

[JAVA] 백준 1786 찾기

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다

validming99.tistory.com

코드

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);
    }
}