[백준][JAVA] 1305번: 광고

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

문제해석

문자열에서 가장 짧은 패턴의 길이를 찾는 문제

KMP 알고리즘과 가장 짧은 패턴은 (문자열길이 -  LSP배열에서의 마지막 요소)라는 것을 알면 쉽게 풀 수 있다.

풀이

LPS 배열이란?

LPS(Longest Prefix which is also Suffix) 배열은 주어진 문자열의 접두사(prefix)와 접미사(suffix)가 일치하는 가장 긴 부분 문자열의 길이를 저장한 배열입니다.

참고: https://mode-creative.tistory.com/25

[알고리즘] KMP알고리즘 (문자열 검색 알고리즘)

 

예시를 통해 이해하기

예를 들어, 문자열 display가 "aaba"라면, LPS 배열을 계산해 보겠습니다:

 

• LPS[0] = 0: 접두사와 접미사가 일치하지 않음.
• LPS[1] = 1: "a"가 접두사와 접미사로 일치.
• LPS[2] = 0: 접두사와 접미사가 일치하지 않음.
• LPS[3] = 1: "a"가 접두사와 접미사로 일치.

이제 가장 짧은 광고의 길이를 찾기 위해 이 정보를 사용해야 합니다.

LPS 배열을 이용한 패턴 길이 계산

LPS 배열의 마지막 값은 주어진 문자열에서 가장 긴 접두사와 접미사가 일치하는 부분 문자열의 길이를 나타냅니다. 예를 들어, 위 예제에서는 LPS[3] = 1이 됩니다. 이는 문자열 "aaba"의 접두사와 접미사가 일치하는 가장 긴 부분 문자열이 "a"임을 의미합니다.

가장 짧은 광고의 길이를 찾기 위해서는 반복되는 패턴을 찾는 것이 중요합니다. 주어진 문자열의 길이에서 LPS 배열의 마지막 값을 빼면 반복 패턴의 길이를 얻을 수 있습니다. 이 패턴은 주어진 문자열의 처음부터 끝까지 나타나는 반복되는 최소 단위입니다.

일반적인 패턴 길이 계산

L - lps[L - 1]를 통해 계산하면 반복되는 패턴의 길이를 얻을 수 있습니다. 이는 주어진 문자열의 전체 길이에서 가장 긴 접두사와 접미사가 일치하는 부분의 길이를 뺀 값입니다.

 

코드

import java.util.Scanner;

public class Main {
    // 부분 일치 테이블(LPS)을 계산하는 메서드
    public static int[] computeLPSArray(String pattern) {
        int M = pattern.length();
        int[] lps = new int[M];
        int length = 0;
        int i = 1;

        lps[0] = 0; // lps[0]은 항상 0

        while (i < M) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = length;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 입력 받기
        int L = scanner.nextInt();
        String display = scanner.next();
        
        // LPS 배열 계산
        int[] lps = computeLPSArray(display);
        
        // 가장 짧은 광고의 길이 계산
        int shortestAdLength = L - lps[L - 1];
        
        // 결과 출력
        System.out.println(shortestAdLength);
        
        scanner.close();
    }
}