poj 1961

この問題はKMPに対する理解を深めることができます.この文字列は、各(each)プレフィックス(prefix)の長さiに対して与えられます. (2<=i)は、このプレフィックスを構成できる最大文字列の数を求めます.例を見ればわかるでしょう.私は他の人を見て初めて知ったのです.具体的には参考にする:
http://jovesky.info/blog/2011/08/25/poj-1961-period-c-language-version/
例:
文字列はa aab aabで、前の2位、つまりa aはaで2回繰り返します.前の6位、つまりaaaabbはabで2回繰り返します.前の9位、つまりaaaababはabで3回繰り返します.前の12位、つまりaaaaaaababはabで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
", testCase++);
        for(i = 2; i <= len; i ++)
            if(next[i] != 0 && i % (i-next[i]) == 0)
                printf("%d %d
", i, i / (i-next[i]));
			printf("
");
    }
    return 0;
}