HDU 3746 KMP 求最少需要在结尾后面补几个字符才能凑成至少两个循环

题意：

T个测试数据

对于每个字符串，问最少需要在结尾补几个字符可以凑成至少2个循环

思路：

最后一个字符对于的是 f【len-1】

而f【len】是表示最后一个字符也和前面匹配了

所以f【len】就表示前缀与后缀的最大匹配，理解这个就方便做了

#include <stdio.h>  
#include <string.h>  
char P[200100];//从0开始存  
int f[200100];//记录P的自我匹配  
int len;  
  
void getFail(const char *p) //前缀函数(滑步函数)  
{  
    int i = 0, j = -1;  
    f[0] = -1;  
    while(i != len)  
    {  
        if(j == -1 || p[i] == p[j]) //(全部不相等从新匹配 || 相等继续下次匹配)  
        {  
            ++i, ++j;  
            if(p[i] != p[j]) //abcdabce  
                f[i] = j;  
            else //abcabca  
                f[i] = f[j];  
        }  
        else  
            j = f[j]; //子串移动到第nextval[j]个字符和主串相应字符比较  
    }  
}  
int main(){  
    int T;scanf("%d",&T);  
  
    while(T--){  
          
        scanf("%s",P);  
        len = strlen(P);  
  
        getFail(P);  
        int lenth = len - f[len];  
        if(len != lenth && len % lenth == 0)  
        { printf("0\n"); continue; }  
          
        printf("%d\n", lenth - (f[len] % lenth));  
          
    }  
    return 0;  
}  
/* 
99 
4 
abab 
6 
ababab 
HDU 3336 必过 

*/

补充：软件开发 , C++ ,