Baekjoon Online Judge

algorithm practice

-問題を逐次解く

34.文字列アルゴリズム1

3.広告

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

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])