写在题目前：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 DAAAAABABAB.

样本输出

143

 

提示

 

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

 

分析：

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

 

CODE：

1 #include
      
        2 #include
       
         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
        
         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<