[BOJ/JAVA] 1701번: Cubeditor

1701번: Cubeditor

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

키워드

어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능

이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램

---

구현

kmp 알고리즘을 이용하여 구현한다.

문자열 알고리즘

용어 정리 |S| 문자열 S의 길이 S = “abcde” 라면 |S| = 5 S[i] (0 ≤ i < |S|) 문자열 S의 i번 글자 S = “abcde” 라면 S[3] = d S[i…j] 문자열 S[i] 부터 S[j] 까지 부분 문자열 S = “abcde” 라면 S[1…3] = bcd S[…a] 문자열 S[0] 부터 S[a] 까지 부분 문자열 S = “abcde” 라면 S[…3] = abcd S[b…] 문자열 S[b] 부터 S[|S|-1] 까지 부분 문자열 S = “abcde” 라면 S[3…] = de 문자열 검색 긴 문자열 H가 문자열 N을 부분 문자열로 포함하는지 확인하는 방법 H = “avava” N = “ava” 라면 N이 출현하는 모든 인덱스를 반환하는 알고리즘을 작성한다고 하자 이때 결과값은..

https://qpdh.tistory.com/115

하지만 메모리를 보면 알 수 있듯이 메모리가 빠듯한 것을 알 수 있다.

따라서 기존 List를 이용하는 대신 int형 배열을 이용한다.

String도 최대한 Buffer를 이용하여 구현한다.

여기서는 kmpSearcg를 사용하지 않는데, getPartialMatch에서 해당 메서드 자체가 pi[i]=N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이 이므로, 해당 값이 2번 나오는 문자열의 최대 길이와 일치한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class java_1701 {

    // pi[i]=N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
    static int getPartialMatch(CharSequence N) {
        int m = N.length();

        int pi[] = new int[m];

        // KMP로 자기 자신을 찾는다.
        // N을 N에서 찾는다. begin=0이면 자기 자신을 찾아버리니까 의미 없음

        int begin = 1, matched = 0;

        // 비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
        while (begin + matched < m) {
            // 현재 문자가 일치하는가?
            if (N.charAt(begin + matched) == N.charAt(matched)) {
                matched++;
                // 문자열의 갱신된 길이 반환
                pi[begin + matched - 1] = matched;
            }
            // 일치하지 않는다면 -> 다음 문자부터 비교 시작
            else {
                // 일치한게 없었다면 -> 단순 다음 문자부터
                if (matched == 0) {
                    begin++;
                }
                // 일치한게 존재했다면..이전 값을 이용하여 갱신해주기
                else {
                    begin += matched - pi[matched - 1];
                    matched = pi[matched - 1];
                }
            }
        }

        int result = 0;
        for (int i = 0; i < pi.length; i++) {
            result = Math.max(result, pi[i]);
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        // 가장 긴 문자열(length-1)부터 부분 문자열이 있는지 찾아보자
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuffer N = new StringBuffer(br.readLine());

        int result = solution(N);

        System.out.println(result);

        br.close();

    }

    // N의 부분 문자열 중 2번 이상 나오는 문자열의 최대 길이 반환
    private static int solution(StringBuffer hayStack) {
        int result = 0;

        // 길이는 N.length()-1부터 시작한다.
        for (int startIndex = 0; startIndex < hayStack.length(); startIndex++) {
            CharSequence needle = hayStack.subSequence(startIndex, hayStack.length());
            result = Math.max(result, getPartialMatch(needle));
        }

        return result;
    }
}

---

Uploaded by N2T