pid=3746">点击打开链接

题意：给T组数据，每组一个字符串，问最少加入多少个字符能够使这个串变成一个子串连续出现的串

思路：利用KMP的next数组进行变换，next数组保存的是眼下为止与字符串从头開始的匹配的程度，也能够看成从头開始的位置。所以假设Next数组最后一个为0，则须要在加入一个这种串才干匹配成功。不然ans=len-Next[len]代表的是不能匹配的后面的串的长度。假设这个长度能够被len取余，则说明这个串已经匹配好了，不然就是这个长度减去取余后的数

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int maxn=200010;

const int mod=10007;

char str1[maxn];

int Next[maxn];

void makenext(int m){

    int i=0,j=-1;

    Next[i]=-1;

    while(i<m){

        if(j==-1||str1[i]==str1[j])

            Next[++i]=++j;

        else j=Next[j];

    }

}

//int KMP(int n,int m){

//    int i=0,j=0,ans=0;

//    while(i<n){

//        if(j==-1||str2[i]==str1[j]) i++,j++;

//        else j=Next[j];

//        if(j==m){

//            ans++;j=Next[j-1];i--;

//        }

//    }

//    return ans;

//}

int main(){

    int T,n;

    scanf("%d",&T);

    while(T--){

        scanf("%s",str1);

        int len=strlen(str1);

        makenext(len);

        if(Next[len]==0){

            printf("%d\n",len);

            continue;

        }

        int ans=len-Next[len];

        if(len%ans==0) printf("0\n");

        else printf("%d\n",ans-len%ans);

    }

    return 0;

}