[BOJ] 1305 : 광고

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

---

KMP 문자열처리

KMP 알고리즘을 이용해 들어온 문자열의 접두사와 접미사가 같은 최대 길이를 구합니다. 그러면, 임의의 광고에서 앞(접두사) 뒤(접미사) 로 공통된 부분의 최대 길이를 구할 수 있고, 나머지 부분은 공통되지않으므로 그냥 덧붙여서 광고를 표현할 수 밖에 없습니다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> getPartialMatch(string N) {
	int m = N.size();
	vector<int> pi(m, 0);
	int begin = 1, matched = 0;
	while (begin + matched < m) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N;
	string L;
	cin >> N >> L;
	vector<int> pi = getPartialMatch(L);
	cout << N - pi[N - 1] << '\n';
	return 0;

}

---