首页 > 代码库 > HDU 1358 next数组的推移

HDU 1358 next数组的推移

题目大意:

输入n,再输入一个长度为n的字符串,从第二位开始,计算它的前缀(包括他自己)中出现过的重复字符串的个数,如aabaabaabaab的第6位的前缀aabaab,aab连续出现了两次,所以输出位数i=6,k=2

 

这个题目要利用next函数求解,不断往前推移,保证往前推移的量能被i整除。

即del=i-next[i];

保证i%del==0;

其实i%del==0成立之后不用多想了,已经可以保证前面是轮回字符串了

在此稍微进行一下理解,如next【9】=6;那么1,2,3位上的元素可以往前移3位,他们与4,5,6上的元素也是对应的。

所以count=i/del,当count>1时将其输出

 

因为我第一次没有理解,其实i%del==0成立之后不用多想了,已经可以保证前面是轮回字符串了这句话,所以仍然不断往前推移del位,其实是无用功,导至TLE

 

错误代码如下:

 1 #include <iostream> 2 #include<cstring> 3  4 using namespace std; 5  6 int next[1000100]; 7 char b[1000100]; 8 int n,time; 9 void getNext(char *b)10 {11     next[0]=0,next[1]=0;12     int j;13     for(int i=1;i<n;i++)14     {15         j=next[i];16         while(j&&b[i]!=b[j]) j=next[j];17         if(b[i]==b[j]) next[i+1]=j+1;18         else next[i+1]=0;19     }20 }21 22 int Gcd(int a,int b)23 {24     if(b==0) return a;25     else return Gcd(b,a%b);26 }27 int main()28 {29     time=1;30     while(cin>>n&&n!=0){31         int t=0,del,count;32         for(int i=0;i<n;i++) cin>>b[i];33 34         getNext(b);35 36         cout<<"Test case #"<<time++<<endl;37 38         for(int i=2;i<=n;i++){39             bool judge=true;40             count=1;41             t=next[i];42             del=i-t;43             while(t){44                 ++count;45                 if(next[t]!=t-del){46                     judge=false;47                     break;48                 }49                 t=next[t];50             }51             if(judge&&count>1) cout<<i<< <<count<<endl;52         }53         cout<<endl;54     }55     return 0;56 }
View Code

 

正确代码如下:

 1 #include <iostream> 2 #include<cstring> 3  4 using namespace std; 5  6 int next[1000100]; 7 char b[1000100]; 8 int n,time; 9 void getNext(char *b)10 {11     next[0]=0,next[1]=0;12     int j;13     for(int i=1;i<n;i++)14     {15         j=next[i];16         while(j&&b[i]!=b[j]) j=next[j];17         if(b[i]==b[j]) next[i+1]=j+1;18         else next[i+1]=0;19     }20 }21 22 int Gcd(int a,int b)23 {24     if(b==0) return a;25     else return Gcd(b,a%b);26 }27 int main()28 {29     time=1;30     while(cin>>n&&n!=0){31         int t=0,del;32         for(int i=0;i<n;i++) cin>>b[i];33 34         getNext(b);35 36         cout<<"Test case #"<<time++<<endl;37 38         for(int i=2;i<=n;i++){39 40             t=next[i];41             del=i-t;42             if(i%del==0&&i/del>1) cout<<i<< <<i/del<<endl;43         }44         cout<<endl;45     }46     return 0;47 }
View Code