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

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 必过

*/