poj 1961

这题可以加深对KMP的懂得！
题意：给出一个字符串，对于它的每个（each）前缀（prefix）长度 i （2<=i），求能由一个子串构成这个前缀的最大字串数量。看例子可以清楚些吧。我是看别人的才知道的。具体看以参考：

http://jovesky.info/blog/2011/08/25/poj-1961-period-c-language-version/

例子：

字符串为aabaabaabaab
前2位也就是aa是a反复2次
前6位也就是aabaab是aab反复2次
前9位也就是aabaabaab是aab反复3次
前12位也就是aabaabaabaab是aab反复4次

解题思路：经由过程KMP的get_next.获得next[]的值。从2开端遍历每个next[i]值，然后用 i-next[j]即获得了反复字串的长度。。。（额，我当初没发明这个啊）。则i/（i-next[j]）即为最大的个数。但同时必须是能整除的。

 

代码如下：

 

#include<iostream>
using namespace std;
const int Max = 1000005;

char str[Max];
int len, next[Max];

void get_next()
{
    int j=1, k=0;
    next[0] = -1;
	next[1]=0;
    while(j<len)
	{
        if(str[j] == str[k])
		{
			next[j+1]=k+1;
            j++; 
			k++;
        }
		else if (k==0)
		{
			next[j+1]=0;
			j++;
		}
        else k=next[k];
    }
}

int main()
{
    int i, testCase = 1;
    while(scanf("%d", &len) && len)
	{
        scanf("%s", str);
        get_next();
        printf("Test case #%d\n", testCase++);
        for(i = 2; i <= len; i ++)
            if(next[i] != 0 && i % (i-next[i]) == 0)
                printf("%d %d\n", i, i / (i-next[i]));
			printf("\n");
    }
    return 0;
}