[백준]광고

백준저지

[광고]https://www.acmicpc.net/problem/1305

• kmp 알고리즘에 대한 정확한 이해가 되어야 풀 수 있는 문제이다.

• kmp 알고리즘은 이전 포스팅에 자세히 설명을 해놨으니 참고 바란다!

• 현재 보이는 문자열 길이에서 “접두사와 접미사가 같은 최대 길이를 빼면” 정답이다.

#include <iostream>
#include <string>

using namespace std;

int * getPi(string p) {
	int * pi = new int[(int)p.size()];
	pi[0] = 0; int j = 0;
	for (int i = 1; i < (int)p.size(); i++) {
		while (p[i] != p[j]) {
			if (j == 0) {
				pi[i] = j;
				break;
			}
			j = pi[j - 1];
		}
		if(p[i] == p[j])
			pi[i] = ++j;
	}
	return pi;
}

int main(void) {
	int in;
	cin >> in;

	string p;
	cin >> p;
	

	int * pi = getPi(p);
	
	cout << in - pi[in - 1] << endl;

	delete(pi);
	return 0;
}