首页 > 代码库 > 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 }
正确代码如下:
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。