[백준 1305] 광고

분류 : kmp

 

요구사항

kmp를 사용하여 접두사 접미사가 같은 길이 구하기

 

풀이

백준 찾기 문제를 풀때 

pi배열을 구하는 거랑 동일하게 풀이한다

 

pi는 !현재 i 길이! 에서 접두사와 접미사가 몇개가 같은지 비교하는것이다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
int pi[10001000];
string n;
string m;
int cnt=0;
void GetPi(){
    int nsize = n.size();
    for(int i=1 ,j=0; i< nsize ; i++){
        while(j>0 && n[i] !=n[j]) j= pi[j-1];
        if(n[i] == n[j]){
            pi[i]=++j;
        }
    }
}

int main(){
    int t;
    cin>>t;
    cin>>n;
  //  cout<<t<<" "<<n<<endl;
    GetPi();
    cout<<t- pi[t-1]<<endl;
}