POJ 2406-Power Strings（重复子串-KMP中的next数组）

Bertha 。 2022-06-17 00:17 167阅读 0赞

Power Strings

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;47642</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;19867</td> 
  </tr> 
 </tbody> 
</table>

Description

Given two strings a and b we define a\*b to be their concatenation. For example, if a = "abc" and b = "def" then a\*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a\*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
    aaaa
    ababab
    .

Sample Output

1
    4
    3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source

[Waterloo local 2002.07.01][]

## 题目意思： ##

一个字符串由K个循环节组成，求循环节最小的时候其字符的个数L。

## 解题思路： ##

暴力又又TLE了，然后，发现要利用next数组的特性：模式串长度为n，其第1位到next\[n\]与模式串第n-next\[n\]位到n位是匹配的。

根据定义，next\[i\]表示模式串0~i-1长度中，后缀与前缀的最长匹配子串的长度，所以next\[n\]表示整个模式串后缀与前缀的最长匹配子串的长度，

next\[KL\] = (K-1)L，即next\[n\] = n - L，所以L = n-next\[n\]，所以n-next\[n\]表示一个最小循环节的长度。

[题解参考][Link 1]

![20170411155843955][]

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 1000010
    char t[MAXN];
    int next[MAXN];
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        while(cin>>t)
        {
            if(t[0]=='.') break;
            memset(next,0,sizeof(next));
            int len=strlen(t);
            int ans=1;
            int p=0,cur;
            next[0]=-1;
            next[1]=0;
            for(cur=2; cur<=len; ++cur)//求next数组
            {
                while(p>=0&&t[p]!=t[cur-1])
                    p=next[p];
                next[cur]=++p;
            }
            if(len%(len-next[len])==0)//模式串第1位到next[n]与模式串第n-next[n]位到n位是匹配的
                ans=len/(len-next[len]);
            cout<<ans<<endl;
        }
        return 0;
    }

[Waterloo local 2002.07.01]: http://poj.org/searchproblem?field=source&key=Waterloo+local+2002.07.01
[Link 1]: http://www.cppblog.com/menjitianya/archive/2014/06/20/207354.html
[20170411155843955]: /images/20220617/755af40a229546b6b8116cbe794dc348.png