http://acm.hdu.edu.cn/showproblem.php?pid=2203
解题报告:由题目:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。移位循环,最多多循环循环一个s1的长度,因此我们可以把s1中的前n-1位直接添加到s1的后面,
如s1=AABCD,可以变为s1=AABCDAABC,这样就包含了所有的情况,然后循环遍历即可。
#include<cstdio> #include<cstring> using namespace std; const int MAX = 100000 + 5; char a[2*MAX],b[MAX]; int next[MAX],len1,len2; void get_next() { int i,j=-1; next[0]=-1; for(int i=1;i<=len2;i++) { while(j>-1&&b[j+1]!=b[i]) { j=next[j]; } if(b[j+1]==b[i]) j++; next[i]=j; } } bool KMP() { get_next(); int i=0,j=-1; for(int i=0;i<2*len1-1;i++) { while(j>-1&&b[j+1]!=a[i]) j=next[j]; if(b[j+1]==a[i]) j++; if(j==len2-1) return true; } return false; } int main() { while(scanf("%s %s",a,b)!=EOF) { len1=strlen(a); for(int j=0;j<len1-1;j++) a[j+len1]=a[j]; len2=strlen(b); if(KMP()) printf("yes\n"); else printf("no\n"); } return 0; }
相关推荐
hdu ACM代码 每种算法都有分类 大三了,没有时间弄ACM,这些要删了
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu动态规划算法集锦
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
杭电ACM 培训课件,包括各种常用的算法,并结合例题详细的讲解,对提高算法思想用很大帮助
算法-数塔(HDU-2084).rar
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
算法-超级楼梯(HDU-2040)(包含源程序).rar
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
算法-六度分离(HDU-1869)(包含源程序).rar
hdu 1574 passed sorce