(简单) POJ 1961 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.

　　题目就是给一个字符串，然后让对从2到N的所有前缀字符串，找出里面的重复串。

　　对于找重复串的问题，用扩展KMP就可以解决。然后就是对于每个前缀，可以证明后面的前缀的最小重复串的长度一定大于等于前面的，因为形成重复串的必要条件就是i+next1[i]>=length 这样的话如果前面不符合这个式子，后面就更不用说了，必须让i增大才可能。

代码如下：

// ━━━━━━神兽出没━━━━━━

//      ┏┓       ┏┓

//     ┏┛┻━━━━━━━┛┻┓

//     ┃           ┃

//     ┃     ━     ┃

//     ████━████   ┃

//     ┃           ┃

//     ┃    ┻      ┃

//     ┃           ┃

//     ┗━┓       ┏━┛

//       ┃       ┃

//       ┃       ┃

//       ┃       ┗━━━┓

//       ┃           ┣┓

//       ┃           ┏┛

//       ┗┓┓┏━━━━━┳┓┏┛

//        ┃┫┫     ┃┫┫

//        ┗┻┛     ┗┻┛

//

// ━━━━━━感觉萌萌哒━━━━━━

// Author        : WhyWhy

// Created Time  : 2015年07月18日 星期六 10时01分22秒

// File Name     : 1961.cpp

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MaxN=;

void EKMP_pre(int m,char s[],int next1[])

{

    int p=,a=,L;

    next1[]=m;

    while(p+<m && s[p]==s[p+])

        ++p;

    next1[]=p;

    for(int k=;k<m;++k)

    {

        L=next1[k-a];

        p=next1[a]+a-(next1[a]!=);

        if(k+L-<p)

            next1[k]=L;

        else

        {

            ++p;

            while(p<m && s[p]==s[p-k])

                ++p;

            next1[k]=p-k;

            a=k;

        }

    }

    next1[m]=;

}

int next1[MaxN];

char s[MaxN];

int N;

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int cas=;

    int minn;

    while(~scanf("%d",&N) && N)

    {

        minn=;

        scanf("%s",s);

        EKMP_pre(N,s,next1);

        printf("Test case #%d\n",cas++);

        for(int i=;i<N;++i)

        {

            while(minn<=i && next1[minn]+minn<i+)

                ++minn;

            if(minn<=i && (i-minn+)%minn==)

                printf("%d %d\n",i+,(i-minn+)/minn+);

        }

        puts("");

    }

    return ;

}

巴特西

(简单) POJ 1961 Period，扩展KMP。

最新文章

热门文章