백준 1305 - Java

 

import java.util.Scanner;

public class BJ1305 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        String input = sc.next();
        sc.close();

        System.out.println(length - getPrefixTable(input, length));
    }

    private static int getPrefixTable(String input, int length) {
        int[] prefixTable = new int[length];
        int j = 0;

        for (int i = 1; i < length; i++) {
            while (j > 0 && input.charAt(i) != input.charAt(j)) {
                j = prefixTable[j - 1];
            }
            if (input.charAt(i) == input.charAt(j)) {
                prefixTable[i] = ++j;
            }
        }
        return prefixTable[length - 1];
    }
}

 

• L: 문자열의 길이를 나타내는 정수
• s: 주어진 문자열:
• 결과는 L - makeTable(s, L)로, 전체 문자열 길이 L에서 가장 긴 접두사-접미사의 길이를 뺀 값을 출력

• KMP 테이블 생성 함수
  • 이 함수는 KMP 알고리즘의 실패 함수(table)을 생성
  • table[i]는 길이 i+1인 문자열의 접미사와 접두사가 동일한 최대 길이를 저장
  • j는 접두사와 접미사의 길이를 추적한다
• 동작 과정:
  • 문자열을 탐색하면서 처음과 끝이 일치하는 최대 길이를 계산한다
  • 만약 두 문자가 일치하지 않으면 j를 table[j - 1]로 업데이트하여 일치하는 접두사 길이를 줄이고, 일치하는 경우 j를 증가시키고 table[i]를 업데이트한다.
• 출력 계산:
  • L - table[L - 1]은 전체 문자열 길이에서 가장 긴 접두사-접미사 길이를 빼, 중복을 제거한 최소 배너 길이를 구하면 된다.