新浪博客 发表时间 --2009-07-28 21:19:38
Power Strings
<wbr><wbr>这道题题目意思很明显,要让我们求最长重复字符串,刚好,老师讲了KMP算法,想想也应该是用KMP算法来解决,但也找不到好的解决办法...</wbr></wbr>
<wbr><wbr>上网查了下,发现了别人的一个思想,就是题目要找最长重复字符串,我们先用字符串长度减去找到的位置,然后用字符串长度来判断是否能整除于它,行的话结果就等于字符串长度除于它,否则就赋值为1...</wbr></wbr>
代码:
<wbr>#include "iostream"<br>
#include "string.h"<br>
using namespace std;<br>
int Getnextval(char str[],int nextval[])<br>
{<br><wbr>int j=0,k=-1,d;<br><wbr>d=strlen(str);<br><wbr>nextval[0]=-1;<br><wbr>while (j<d)<br><wbr>{<br><wbr><wbr>if (k==-1||str[j]==str[k])<br><wbr><wbr>{<br><wbr><wbr><wbr>j++;<br><wbr><wbr><wbr>k++;<br><wbr><wbr><wbr>if (str[j]!=str[k])<br><wbr><wbr><wbr>{<br><wbr><wbr><wbr><wbr>nextval[j]=k;<br><wbr><wbr><wbr>}<br><wbr><wbr><wbr>else<br><wbr><wbr><wbr><wbr>nextval[j]=nextval[k];<br><wbr><wbr>}<br><wbr><wbr>else<br><wbr><wbr><wbr>k=nextval[k];<br><wbr>}<br><wbr>j-=k;<br><wbr>return j;<br>
}<br>
int main()<br>
{<br><wbr>char str[1000001];<br><wbr>int a[1000000],d,h,i,max;<br><wbr>while (1)<br><wbr>{<wbr><wbr><br><wbr><wbr>gets(str);<br><wbr><wbr>if (str[0]=='.'&&str[1]=='\0')<br><wbr><wbr>{<br><wbr><wbr><wbr>break;<br><wbr><wbr>}<br><wbr><wbr>d=strlen(str);<br><wbr><wbr>h=Getnextval(str,a);<br><wbr><wbr>if (d%h==0)<br><wbr><wbr>{<br><wbr><wbr><wbr>h=d/h;<br><wbr><wbr>}<br><wbr><wbr>else<br><wbr><wbr><wbr>h=1;<br><wbr><wbr>printf("%d\n",h);<br><wbr>}<br><wbr>return 0;<br>
}</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
分享到:
相关推荐
很有用的解题报告。。是acm初级提高的必备资料。。。。。
ACM-ICPC 历年竞赛 真题,各大赛区真题详解,内含几大赛区各年度的真题
Algorithm-203-ACM-Problems-Code.zip,203个ACM问题的C 源代码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
个人ACM-ICPC模板acm-icpc-master.zip
杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt
2015北大ACM-ICPC暑期课 pdf
2010年第34届ACM-icpc程序设计大赛全球总决赛试题
ACM-ICPC 历年竞赛 真题,各大赛区真题详解,内含几大赛区各年度的真题
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
ACM-ICPC培训资料汇编
ACM_ACM-ICPC算法示例之Greedy_题解
ACM_ACM-ICPC算法示例之Hashing_题解
Algorithm-ACM-ICPC.zip,感觉自己做假题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
ACM-ICPC要求的知识点 ACM/ICPC要求的知识点 排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序) 数论(整除,集合论,关系,素数,进位制,辗转相除,...
ACM----博弈论
2008 ACM-ICPC East Central North America 包含题目、测试数据、解答
ACM---算法数论
ACM-ICPC_algorithm 算法模板。 阅读对象:专门的算法爱好者。如果是只为求职的可不下载
湖南师大数计院ACM—ICPC个人邀请赛题目及解答,非常的不错哦,详细的代码和解题报告,题目有的很巧妙,这套题目比较重数学~~