1305 광고

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

길이가 N인 광고판이 있고 광고(문자열)가 광고판을 꽉 채우면서 반복되서 나타난다. 이 때 가능한 광고의 길이 중 가장 짧은 것을 찾는 문제이다. 광고가 반복해서 밀려나면서 뒤에서도 나타난다. 따라서 광고판에서 prefix와 suffix가 같을 때 길이의 최대값을 구하고 N에서 이를 빼주면 가장 짧은 광고의 길이이다. 이는 KMP에서 실패 함수의 정의이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    int n;
    string s;
    cin>>n>>s;
    vector<int> pi(n);
    pi[0]=0;
    for(int i=1,j=0;i<n;i++)
    {
        while(j>0 && s[i]!=s[j]) j=pi[j-1];
        if(s[i]==s[j]) pi[i]=++j;
        else pi[i]=0;
    }
    cout<<n-pi[n-1]<<'\n';
    return 0;
}