数据结构之KMP算法---poj2406---Power Strings-白红宇的个人博客

发布日期：2022-02-02 02:58:09 浏览次数：2 分类：技术文章

本文共 1253 字，大约阅读时间需要 4 分钟。

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

abcdaaaaababab.

Sample Output

代码实现：

#include
   
    #include
    
     #define max 1000001using namespace std;int next[max];char str[max];int getnext(char *str){
     
int i=0,j=-1;
     
int len=strlen(str);
     
next[0]=-1;
     
while(i
     
      
{
      
if(j==-1||str[i]==str[j])
      
{
      
i++;
      
j++;
      
next[i]=j;
      
}
      
else
      
j=next[j];
      
}
      
i=len-j;
      
if(len%i==0)
      
return len/i;
      
else
      
return 1;}int main(){
      
while(cin>>str)
      
{
      
if(str[0]=='.')break;
      
int ans=getnext(str);
      
cout<
      
       <
       
        
}
        
return 0;}

转载地址：https://blog.csdn.net/u010368749/article/details/19341149 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：KMP算法的next[]数组通俗解释

下一篇：数据结构之字典树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

最新文章