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]) //abcdabcef[i] = j;else //abcabcaf[i] = f[j];}elsej = 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;}/*994abab6abababHDU 3336 必过*/