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

喜欢ヅ旅行 2022-05-19 07:06 168阅读 0赞

[传送门][Link 1]

题意：给你一个长度为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;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1358