[HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)

发布于 2018-02-20  105 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A K , that is A concatenated K times, for some string A. Of course, we also want to know the period K.

Http

HDU
UVA
SPOJ
POJ
ZOJ

Tag

KMP

题目大意

给出一个字符串,求所有能表示成若干循环串的前缀以及这些前缀的循环节个数。

解决思路

我们知道\(KMP\)算法求出的\(Next\)数组表示的是这个前缀的最长相同前缀后缀,那么,如果i是\(i-Next[i]\)的非\(1\)整数倍,就说明以\(i\)结尾的这个前缀是一个循环串,循环节长度为\(i-Next[i]\),循环节个数就为\(\frac{i}{i-Next[i]}\)。
为什么这样是对的呢?比如下面这个前缀
HDU-1358-1
根据\(Next[i]\)的定义,那么前面长度为\(L'\)的前缀\([1,L']\)一定与\([L'+1,2L']\)这一段相同,就是下面紫色和黄色的段。
HDU-1358-1
那么同理又有\([2L'+1,3L']\)相同,即下面黄色与橙色段。
HDU-1358-1
依次类推,可知如果\(L\)是\(L'\)的倍数,那么这个前缀就一定是循环的。

## 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1001000;
const int inf=2147483647;

int n;
char str[maxN];
int F[maxN];

int main()
{
    int cas=0;
    ios::sync_with_stdio(false);
    while (cin>>n)
    {
        if (n==0) break;
        cin>>(str+1);
        F[1]=0;F[0]=-1;
        for (int i=2;i<=n;i++)//得到Next数组
        {
            int j=F[i-1];
            while ((j!=0)&&(str[j+1]!=str[i])) j=F[j];
            if (str[j+1]==str[i]) F[i]=j+1;
            else F[i]=0;
        }
        printf("Test case #%d\n",++cas);
        for (int i=2;i<=n;i++)
            if ((F[i]!=0)&&(i%(i-F[i])==0)) printf("%d %d\n",i,i/(i-F[i]));
        printf("\n");
    }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)


HNCJ OIer 一枚