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

HDU 1358 next数组的推移

2024-07-13 14:01:11   220人阅读

题目大意：

输入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


联系
我们