백준 1305 광고

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

※선행해야 할 알고리즘 : KMP Algorithm

Algorithm : 문자열의 pattern table을 구한 후 그 해당하는 pattern table값을 문자열 길이에서 빼준다.

1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음.

2. 예를 들어

aabaaa에서 보면 pi=2, prefix suffix가 같은 최대의 부분 문자열이 aa이다. 

길이가 N인 광고가 계속 이어져 있는 것을 생각하면 prefix aa는 앞 광고의 suffix aa로 볼 수도 있을 것이다. 즉, baaa가 원래 광고이고, baaa앞의 aa는 baaa의 suffix aa가 채우고 있는 것으로 볼 수 있는 것이다.

3. 따라서 소스코드는 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<cstdio> #include<vector> #include<string> using namespace std; vector<int>maketable(string s, int L) { vector<int> table(s.size(), 0); int j = 0; for (int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) j = table[j - 1]; if (s[i] == s[j]) table[i] = ++j; } return table; } int main() { int L; string s; cin >> L >> s; auto p = maketable(s, L); cout << L - p[L - 1] << endl; return 0; }