首页 > 其他 > 详细

PKU 2406 Power Strings(KMP最长循环不重叠字串)

时间:2016-07-19 18:53:25      阅读:137      评论:0      收藏:0      [点我收藏+]

题意:给一个字符串S长度不超过10^6,求最大的n使得S由n个相同的字符串a连接而成,如:"ababab"则由n=3个"ab"连接而成,"aaaa"由n=4个"a"连接而成,"abcd"则由n=1个"abcd"连接而成。

利用KMP算法,求字符串的特征向量next,若len可以被len - next[len]整除,则最大循环次数n为len/(len - next[len]),否则为1。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 1000002;
int next[N];
char S[N], T[N];
int slen, tlen;

void kmp_pre(char x[],int m,int Next[])
{
    int i,j;
    j=Next[0]=-1;
    i=0;
    while(i<m)
    {
        while(-1!=j&&x[i]!=x[j]) j=Next[j];
        Next[++i]=++j;
    }
}

int main()
{

    while(~scanf("%s",S))
    {
        int n=strlen(S);
        if (n==1&&S[0]==.)
        {
            break;
        }


        kmp_pre(S,n,next);

        if (n%(n-next[n])==0)
        {
            printf("%d\n",n/(n-next[n]));
        }
        else
        {
            puts("1");
        }

    }

    return 0;
}

 

PKU 2406 Power Strings(KMP最长循环不重叠字串)

原文:http://www.cnblogs.com/s1124yy/p/5685765.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!