Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

3. 광고

1305번

KMP의 failure function을 활용하는 문제 2

이번 문제는 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 문제이다.

문자열에서 접두사 - 접미사가 같은 문자열의 최대 길이를 구하면 된다.
문자열 안에 똑같은 패턴이 있다면 가장 짧은 패턴을 찾아내는 것이다. 패턴의 길이 최대는 N

KMP 알고리즘을 활용하여 구현할 수 있다. Pi 배열을 이용한다.

Java / Python

• Java

import java.io.*;

public class Main {
	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		String str = br.readLine();

		// KMP 알고리즘
		// 접두사&접미사 동일한 문자열 최대 길이 구하기
		int[] pi = getLastPi(str);
		bw.write(N - pi[N - 1] + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	// pi배열 최대 패턴의 길이 구하기
	static int[] getLastPi(String ptn) {
		int j = 0;
		int len = ptn.length();
		int[] pi = new int[len];

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

• Python

import sys
input = sys.stdin.readline

def getPi(P):
    pi = [0 for _ in range(0, len(P))]
    j = 0
    
    for i in range(1, len(P)):
        while j > 0 and P[i] != P[j]:
            j = pi[j - 1]

        if (P[i] == P[j]):
            j += 1
            pi[i] = j
    return pi

N = int(input())
ptn = input()
print(N - getPi(ptn)[N-1])