kmp与最小循环节

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;

const int N=1e6+10,INF=0x3f3f3f3f;

char s2[N];
int d[N];//d[i]表示以i结尾的字符串中 最大公共前后缀的长度

void init()//得到模式串的d[] 下标是从0开始的
{
    int len=strlen(s2);
    int i=1,j=0;//两个s2串
    while(i<len)
    {
        if(s2[i]==s2[j])
            d[i++]=++j;
        else {
            if(j>0) j=d[j-1];
            else i++;
        }
    }
}

int main()
{
    int n;  //字符串长度

    cin>>n;

    scanf("%s",s2);//输入字符串

    init();//获得d[]数组

    cout<<n-d[n-1]<<endl;//表示长度为ns2的字符串的最小循环节

    return 0;
}