扩展kmp模板

#include <iostream>
#include <string.h>
using namespace std;
const int maxn=1100;
int Next[maxn],extend[maxn];
void get_Next(char *s)
{
    int n=strlen(s);
    int i,j,k;
    for(j=0;1+j<n&&s[j]==s[1+j];j++);
    Next[1]=j;
    k=1;
    for(i=2;i<n;i++)
    {
        int len=k+Next[k],L=Next[i-k];
        if(L<len-i)
        {
            Next[i]=L;
        }
        else
        {
            for(j=max(0,len-i);i+j<n&&s[j]==s[i+j];j++);
            Next[i]=j;
            k=i;
        }
    }
    Next[0]=n;
}
void ex_kmp(char *T,char *s)
{
    int n=strlen(T),m=strlen(s);
    int i,j,k;
    for(j=0;j<n&&j<m&&T[j]==s[j];j++);
    extend[0]=j;
    k=0;
    for(i=1;i<n;i++)
    {
        int len=k+extend[k],L=Next[i-k];
        if(L<len-i)
        {
            extend[i]=L;
        }
        else
        {
            for(j=max(0,len-i);j<m&&i+j<n&&s[j]==T[i+j];j++);
            extend[i]=j;
            k=i;       
        }
    }
        
}
//定义母串为s,字串为T，s的长度为n，T的长度为m,求T与S的每一个后缀的最长公共前缀
//设extend数组，extend[i]表示T与S[i,n-1]的最长公共前缀，i从0到n-1，如果有一个extend[i]=m,则T在S中在i位置出现。
int main() 
{
    char s[maxn],T[maxn];
    cin>>T>>s;  //找出T的所有后缀与s的最长公共前缀 
    get_Next(s);
    ex_kmp(T,s);
    for(int i=0;i<strlen(T);i++)
    {
        cout<<extend[i]<<" ";
    }
    cout<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
void getfail(char *p,int *fail)
{
    int match=-1;
    fail[0]=-1;
    for(int i=1;p[i];i++)
    {
        while(match>=0&&p[match+1]!=p[i])
        {
            match=fail[match];
        }
        if(p[match+1]==p[i])
        match++;
        fail[i]=match; 
    }
}

int main()
{
    char s[maxn];
    int fail[maxn];
    cin>>s;  //对s进行去重，len2是去重后长度 
    getfail(s,fail);
    int len=strlen(s),len2;
    len2=len-fail[len-1]-1;
    if(len%len2!=0)len2=len;
    cout<<len2<<endl;
    return 0;
}

int get_Next(char *s)
{
    int n=strlen(s),ans=0;
    int i,j,k;
    for(j=0;1+j<n&&s[j]==s[1+j];j++);
    Next[1]=j;
    k=1;
    for(i=2;i<n;i++)
    {
        int len=k+Next[k],L=Next[i-k];
        if(L<len-i)
        {
            Next[i]=L;
        }
        else
        {
            for(j=max(0,len-i);i+j<n&&s[j]==s[i+j];j++);
            Next[i]=j;
            k=i;
        }
        if(Next[i]>ans)
        ans=Next[i];
    } 
    Next[0]=n;
    return ans;
}