题意：给出一段字符串  求最少在最右边补上多少个字符使得形成循环串（单个字符不是循环串）

 

自己乱搞居然搞出来了。。。

想法是：  如果nex【len】为0  那么答案显然是补len

否则  答案为循环节的长度-nex【len】 小于0变0

 

写了一个假算法居然能过    。。。 ababca就错了

 

kmp重要性质：

重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾)，另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);

abcabcabc 为3

abcbca 为5

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
#define N 100000+50
int nex[N];
int lenp,lens;
char p[N];
void getnext()
{
    lenp=strlen(p);
    nex[0]=-1;
    int k=-1,j=0;
    while(j<lenp)
    {
        if(k==-1||p[j]==p[k])
            nex[++j]=++k;
        else k=nex[k];
    }
}
int main()
{
    int n;
    RI(n);
    while(n--)
    {
        RS(p);
        getnext();
        if(nex[lenp]==0)
        {
            printf("%d\n",lenp);
            continue;
        }
        int cnt=lenp-nex[lenp];//最小循环节
        
        printf("%d\n",(cnt-lenp%cnt)==cnt?0:cnt-lenp%cnt);
    }
    return 0;
}

View Code