COGS 1710. [POJ2406]字符串的幂

★☆ 输入文件：powerstrings.in 输出文件：powerstrings.out 简单对比
时间限制：3 s 内存限制：256 MB

【题目描述】

对于给定的两个字符串a,b，我们定义a*b是将把它们连接在一起形成的字符串。例如，若a="abc"，b="def"，则a*b="abcdef"。如果我们将这种运算视为乘法，则非负整数的乘方运算被以类似的方式定义：a^0=""（空字符串），a^(n+1)=a*(a^n)。

【输入格式】

输入包含多组数据。

每组数据有一行一个大写字母组成的字符串s，其长度至少为1，至多为10^6.输入结束标志为一行一个“.”（半角句号）。

【输出格式】

输出使得存在某个a，使得a^n=s的最大n。

【样例输入】

ABCD

AAAA

ABABAB

.

【样例输出】

【提示】

输入文件可能很大，请使用scanf代替cin以避免超时。

【来源】

POJ 2406 Power Strings

还是不会巧方法。。

其实观察一下next数组就发现他的神奇。。

（1）若2*next[len] < len 则最小重复单元长度为len那么他重复次数为1

（2）若2*next[len] > len 则：

　　1>:如果len%(len-next[len]) == 0则最小重复单元长度为len - next[len]，那么其重复次数为len/(len-next[len]).

　　2>：如果len%(len - next[len]) != 0 则最小重复单元长度为：len，那么其重复次数为1

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

#define N 1000005

char str[N];

int Next[N];

void Get_next(int ln)

{

    int i=,j=-;

    Next[i]=j;

    for(;i<ln;)

    {

        if(j==-||str[i]==str[j]) i++,j++,Next[i]=j;

        else j=Next[j];

    }

}

int main()

{

    for(;;)

    {

        scanf("%s",str);

        if(str[]=='.') break;

        int len=strlen(str);

        Get_next(len);

/*        for(int i=1;i<=len;i++) printf("%d ",Next[i]);

        printf("\n");*/

        if(*Next[len]<len) printf("1\n");

        else

        {

            if(len%(len-Next[len])==) printf("%d\n",len/(len-Next[len]));

            else printf("1\n");

        }

    }

    return ;

}

巴特西