HDU 3746 Cyclic Nacklace(KMP求最微循环元)

HDU 3746 Cyclic Nacklace(KMP求最小循环元)

/*
题意：组成一个环，要求至少包含两个相同字符串，求至少向给出字符串后面添加的字符数

题解：根据KMP求出循环元，最小循环元t = len - next[len]。然后问题就很容易解决了。
做完这道题，感触更深一些了，这个公式对任何字符串都适用。
*/

#include <iostream>
using namespace std;
const int nMax = 100010;
int T;
char s[nMax];
int next[nMax];

void getNext(char *s, int *next, int len)
{
	int i, j;
	i = 0, j = -1;//j需要从-1开始，需要跟前一位比较
	next[0] = -1;
	while(i < len)
	{
		if(j == -1 || s[i] == s[j])
		{
			i ++;
			j ++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int main()
{
	//freopen("e://data.in", "r", stdin);
	scanf("%d", &T);
	while(T --)
	{
		scanf("%s", s);
		int len = strlen(s);
		getNext(s, next, len);
		int t = len - next[len];//KMP求出循环元，len - next[len]即为循环元
		if(len % t == 0)
		{
			if(len == t) printf("%d\n", len);
			else printf("0\n");
		}	
		else
		{
			t =t - len % t;
			printf("%d\n", t);
		}
	}
}

1楼dwt520f昨天 22:17

wewewe