HDU3746 -- Cyclic Nacklace

原題位址：http://acm.hdu.edu.cn/showproblem.php?pid=3746

題意：

給你一串手鍊，每個英文字母代表一個顔色，問你需要至少補多少個珠子能夠将手鍊變為循環的，比如abca需要補上ab才能成為循環的，而aaa就不需要補珠子了。

這個題用的方法是使用KMP的求Next數組的方法來做題。

對于Next數組我們隻需要看最後一個數字就行了。最後一個數字會有三種可能，第一種是0，第二種是字元串長度減去Next[len]後可被len整除，第三種就是不能被整除。

第一種時，說明後面出現了若幹個前面都沒有的顔色的珠子，比如abcabcde前面确實是一個循環，但是到了de的時候出現了前面沒有的珠子，如果想弄成循環必須補成abcabcdeabcabcde的形式，也就是補長度為len的珠子。

第二種時，用字元串長度減去Next[len]的到的其實是循環節的長度，為什麼呢？舉個例子，比如abcabca，len = 7,next數組為{-1， 0， 0， 0， 1， 2， 3， 4}，當我用len-4的時候，得到的是3，也就是最小循環節的長度。怎麼了解呢，你想第一個循環節的next值一定全都是為0的，而後面又是一直符合循環條件的，隻要符合循環條件，那個i就是一直在加一，這個時候Next[len]實際就是去掉一個循環之後的長度。是以用字元串長度減去Next[len] 就是一個循環節的長度。當結果可被len整除時，說明這個手鍊符合條件，不需要添加珠子。

第三種同上。

AC代碼：

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 500001;
int Next[MAX_N];
char s[MAX_N];

void GetNext(char *s)
{
	int k = -1, j = 0;
	int len = strlen(s);
	
	Next[0] = -1;
	//這裡的珠子我們看的時最後一個，是以循環不能在是len-1了
	while (j < len)
	{
		if (k == -1 || s[j] == s[k])
		{
			j++;
			k++;
			Next[j] = k;
		}
		else
		{
			k = Next[k];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	
	int t;
	
	cin >> t;
	
	while (t--)
	{
		cin >> s;
		
		int len = strlen(s);
		
		GetNext(s);
		
		if (Next[len] == 0)
		{
			cout << len << endl;
		}
		else
		{
			int t = len - Next[len];
			
			if (len % t == 0)
			{
				cout << "0" << endl;
			}
			else
			{
				cout << t - len % t << endl;
			}
		}
	}
	
	return 0;
}