POJ 2406 Power Strings——————KMP next数组的利用

灰太狼 2022-05-16 09:15 156阅读 0赞

**Power Strings**

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      Language:Default 
    </div> 
    <div>
      Power Strings 
    </div> 
    <div> 
     <table> 
      <tbody> 
       <tr> 
        <td><b>Time Limit:</b> 3000MS</td> 
        <td></td> 
        <td><b>Memory Limit:</b> 65536K</td> 
       </tr> 
       <tr> 
        <td><b>Total Submissions:</b> 58445</td> 
        <td></td> 
        <td><b>Accepted:</b> 24302</td> 
       </tr> 
      </tbody> 
     </table> 
    </div><p>Description</p> 
    <div>
      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). 
    </div><p>Input</p> 
    <div>
      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. 
    </div><p>Output</p> 
    <div>
      For each s you should print the largest n such that s = a^n for some string a. 
    </div><p>Sample Input</p><pre>abcd
aaaa
ababab
.
</pre><p>Sample Output</p><pre>1
4
3
</pre><p>Hint</p> 
    <div>
      This problem has huge input, use scanf instead of cin to avoid time limit exceed. 
    </div><p>Source</p> 
    <div> 
     <a rel="nofollow">Waterloo local 2002.07.01</a> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

--------------------

next数组的利用

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN=1e6+7;
    char s[MAXN];
    int slen,nex[MAXN];
    
    void GetNext()
    {
        int i,j;
        i=0;
        j=nex[0]=-1;
        while(i<slen)
        {
            while(-1!=j && s[i]!=s[j])  j=nex[j];
            nex[++i]=++j;
        }
    }
    int main()
    {
        while(~scanf("%s",s)&&s[0]!='.')
        {
            slen=strlen(s);
            GetNext();
            int L=slen-nex[slen];//可能得最长长度循环子串
    //        printf("%d\n",slen/L);//不能直接这样输出，不然遇到abcabcabcab这样的情况，会WA的
            int ans=1;
            if(slen%L==0)   ans=slen/L;//必须得先判断一下
            printf("%d\n",ans);
        }
        return 0;
    }