[백준OJ] 1305번 광고

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

1305번: 광고

---

 

-풀이-

L인 전광판에는 광고가 (광고 + 광고의 접두사) 로 이루어져있기때문에 , 가능한 광고의 길이의 최소를 구하기 위해서는 , L- (전광판 문자열에서 접두사와 접미사가 일치하는 최대 길이)를 구해주면 된다.

이때 전광판 문자열에서 접두사와 접미사가 일치하는 최대 길이는 KMP알고리즘을 이용해주면 된다.

 

-시간복잡도-

O(L)

 

-코드-

#include <iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

vector<int> getPi(string p) {
	int m = p.size(), j = 0;
	vector<int> pi(m, 0);
	for (int i = 1; i < m; i++) {
		while (j > 0 && p[i] != p[j]) {
			j = pi[j - 1];
		}
		if (p[i] == p[j]) {
			pi[i]=++j;
		}
	}
	return pi;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;
	string s;
	cin>> s;

	auto pi = getPi(s);

	cout << n-pi[n-1];

	return 0;
}