字符串(扩展KMP):HDU 4333 Revolving Digits
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了字符串(扩展KMP):HDU 4333 Revolving Digits,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3704字,纯文字阅读大概需要6分钟。
内容图文
![字符串(扩展KMP):HDU 4333 Revolving Digits](/upload/InfoBanner/zyjiaocheng/1069/41912f31c46d43af9a5de435301c6777.jpg)
Revolving Digits
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24729 Accepted Submission(s): 5381
For each test cases, there is only one line that is the original integer N. we will ensure that N is an positive integer without leading zeros and N is less than 10^100000.
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4usingnamespace std; 5constint maxn=200010; 6int lens,lent,Q,p,cas; 7int f[maxn],r[maxn]; 8char s[maxn],t[maxn]; 9struct ExKmp{ 10void Init(){ 11 memset(f,0,sizeof(f)); 12 memset(r,0,sizeof(r)); 13 s[lens+1]=‘%‘;t[lent+1]=‘&‘; 14 } 1516void Get_Fail(){ 17 f[1]=lent; 18while(t[2+f[2]]==t[1+f[2]]) 19 f[2]+=1;p=2; 20for(int i=3;i<=lent;i++){ 21int k=p+f[p]-1,L=f[i-p+1]; 22if(i+L-1<k)f[i]=L; 23else{ 24 f[i]=max(0,k-i+1); 25while(t[1+f[i]]==t[i+f[i]]) 26 f[i]+=1;p=i; 27 } 28 } 29 } 3031void Exkmp(){ 32 Init();Get_Fail(); 33while(s[1+r[1]]==t[1+r[1]]) 34 r[1]++;p=1; 35for(int i=2;i<=lens;i++){ 36int k=p+r[p]-1,L=f[i-p+1]; 37if(i+L-1<k)r[i]=L; 38else{ 39 r[i]=max(0,k-i+1); 40while(t[1+r[i]]==s[i+r[i]]) 41 r[i]+=1;p=i; 42 } 43 } 44 } 45}kmp; 4647int fail[maxn]; 48int Get_Rnd(){ 49 fail[1]=fail[2]=1; 50for(int i=2;i<=lent;i++){ 51int j=fail[i]; 52while(j!=1&&t[i]!=t[j])j=fail[j]; 53 fail[i+1]=t[i]==t[j]?j+1:1; 54 } 55if(lent-fail[lent]==0||lent%(lent-fail[lent])) 56return1; 57else58return lent/(lent-fail[lent]); 59} 6061void Solve(){ 62 kmp.Exkmp(); 63int rnd=Get_Rnd(); 64int ans1=0,ans2=0,ans3=0; 65for(int i=1;i<=lent;i++){ 66if(r[i]==lent)ans2++; 67elseif(s[i+r[i]]<t[r[i]+1])ans1++; 68elseif(s[i+r[i]]>t[r[i]+1])ans3++; 69 } 70 printf("%d %d %d\n",ans1/rnd,ans2/rnd,ans3/rnd); 71} 7273int main(){ 74 scanf("%d",&Q); 75while(Q--){ 76 scanf("%s",t+1); 77 lent=strlen(t+1); 78for(int i=1;i<=lent;i++) 79 s[i]=s[lent+i]=t[i]; 80 printf("Case %d:",++cas); 81 lens=lent*2;Solve(); 82 } 83return0; 84 }
原文:http://www.cnblogs.com/TenderRun/p/5698568.html
内容总结
以上是互联网集市为您收集整理的字符串(扩展KMP):HDU 4333 Revolving Digits全部内容,希望文章能够帮你解决字符串(扩展KMP):HDU 4333 Revolving Digits所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。