Hdu 1358 Period(KMP Next数组的理解)-蒲公英云

Hdu 1358 Period(KMP Next数组的理解)

传送门

题意：给你一个长度为n的（2 <= N <= 1 000 000）字符串，求字符串的所有前缀字符串中字能刚好由k（k>1）个循环节构成的字符串，输出这些k。

分析：由于题目要求k最大，那么其实就是求最小循环节，由于N很大很明显我们不能用暴力解决，我们想到Next数组其实是存了每个子串的前后缀匹配信息的，以i结尾的字符串它的最小循环节minPeriod的长度其实就是 i-Next[i] ，所以我们只需要i从小到大扫一遍如果当前 i 能够整除最小循环节，就说明这个子串能够由最小循环节通过循环组成，那么就输出最小循环节循环的次数。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
char t[maxn];
int Next[maxn];
int N;
void getNext()
{
    int j = -1,i = 0;
    Next[0] = -1;
    while(i<N)
    {
        if(j==-1||t[i]==t[j])
        {
            ++i;
            ++j;
            Next[i]=j;
        }
        else j = Next[j];
    }
}
int main()
{
    int kase = 0;
    while(scanf("%d",&N)&&N)
    {
        scanf("%s",t);
        getNext();
        printf("Test case #%d\n",++kase);
        for(int i=2;i<=N;i++)
        {
            int minPeriod=i-Next[i];
            if(i%minPeriod==0&&i/minPeriod!=1)/**题目要求中 K>1*/
            {
                printf("%d %d\n",i,i/minPeriod);
            }
        }
        printf("\n");
    }
    return 0;
}