Power Strings-蒲公英云

Power Strings

写在题目前：POJ太好用啦！

描述

给定两个字符串a和b，我们将* b定义为它们的串联。例如，如果a =“abc”而b =“def”则a * b =“abcdef”。如果我们将连接视为乘法，则以正常方式定义非负整数的取幂：a ^ 0 =“”（空字符串）和^（n + 1）= a *（a ^ n）。

输入

每个测试用例都是一行输入，表示s，一串可打印的字符。s的长度至少为1，不超过1百万个字符。包含句点的行在最后一个测试用例之后。

输出

对于每个s，您应该打印最大的n，使得某些字符串a的s = a ^ n。

样本输入

A B C D
AAAA
ABABAB
.

样本输出

1
4
3

提示

这个问题有很大的输入，使用scanf而不是cin来避免时间限制超过。

分析：

本题要求对于KMP有详细理解，尤其是对于它的P数组理解，以此计算答案。

CODE：

1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int M=1000005;
 5 char a[M];
 6 int p[M],n;
 7 int main(){
 8     while (1){
 9         cin>>a+1;
10         if (a[1]=='.') break;
11         n=strlen(a+1);
12         p[1]=0;
13         int j=0;
14         for (int i=1;i<n;i++){
15             while (j>0&&a[j+1]!=a[i+1]) j=p[j];
16             if (a[j+1]==a[i+1]) j++;
17             p[i+1]=j;
18         }
19         if (n%(n-p[n])==0) cout<<n/(n-p[n])<<endl;
20         else cout<<1<<endl;
21     }
22     return 0;
23 }