博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU_2203_KMP入门
阅读量:5821 次
发布时间:2019-06-18

本文共 1244 字,大约阅读时间需要 4 分钟。

亲和串

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 12533    Accepted Submission(s): 5667

Problem Description
人随着岁数的增长是越大越聪明还是越大越笨,这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考,因为他在很小的时候就知道亲和串如何判断了,但是发现,现在长大了却不知道怎么去判断亲和串了,于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。
 

 

Input
本题有多组测试数据,每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2,s1与s2的长度均小于100000。
Output
如果s2是s1的亲和串,则输出"yes",反之,输出"no"。每组测试的输出占一行。
 

 

Sample Input
AABCD
CDAA
ASD
ASDF
 

 

Sample Output
yes
no
 
#include
#include
#include
#include
#include
#include
#include
using namespace std;char a[200005],b[100005];int Next[100005];void getNext(){ memset(Next,-1,sizeof(Next)); //!!!下标从0开始和从1开始,初始化数组不同,在这TLE了好久 int m=strlen(b),k=-1; for(int i=1; i
-1&&b[k+1]!=b[i]) k=Next[k]; if(b[k+1]==b[i]) k++; Next[i]=k; }}void CMP(){ getNext(); int n=strlen(a),m=strlen(b),k=-1; for(int i=0; i
-1&&b[k+1]!=a[i]) k=Next[k]; if(b[k+1]==a[i]) k++; if(k==m-1) { puts("yes"); return; } } puts("no");}int main(){ while(scanf("%s%s",a,b)!=EOF) { CMP(); } return 0;}

 

 
 

转载于:https://www.cnblogs.com/jasonlixuetao/p/5905740.html

你可能感兴趣的文章
cocos2d-x JS 开启远程代码调试
查看>>
手机H5,用Jquery使图片自动填满两栏式排版
查看>>
ios 沙盒路径
查看>>
CSS选择器,选择器的优先级
查看>>
【368】相关术语说明
查看>>
ASP.NET的必须知道的东东(HttpModule,HttpHandler)
查看>>
linux---finger命令
查看>>
Artech的MVC4框架学习——第四章Model元数据的解析
查看>>
“将截断字符串或二进制数据”错误分析
查看>>
html5 页面总结
查看>>
matlab练习程序(Hilbert图像置乱)
查看>>
【WP之一】]独立存储
查看>>
关于网页关闭的弹窗
查看>>
线段树练习
查看>>
【2019-06-04】内心的纠结
查看>>
JSP2.0自定义标签
查看>>
aop的概念以及 cglib-nodep-2.1_3.jar第三方jia包动态代理使用
查看>>
Qin Shi Huang's National Road System HDU - 4081(树形dp+最小生成树)
查看>>
nohup和&后台运行,进程查看及终止
查看>>
linux安装mysql全纪录[包括yum和rpm安装,编码,远程连接以及大小写问题]
查看>>