HDU 2203 kmp
2024-10-21 10:38:22
http://acm.hdu.edu.cn/showproblem.php?pid=2203
亲和串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15601 Accepted Submission(s): 6895
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
CDAA
ASD
ASDF
Sample Output
yes
no
no
Author
Eddy
将这个循环串乘以二在做一次kmp匹配就好了,能想到这一点就很简单了。
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int nex[],l1,l2,sl;
char s1[],s2[];
void solve()
{
int i,j,sz=l2;
nex[]=nex[]=;
for(i=;i<sz;++i)
{
j=nex[i];
while(j&&s2[i]!=s2[j]) j=nex[j];
nex[i+]=s2[i]==s2[j]?j+:;
}
j=;
for(i=;i<l1;++i)
{
while(j&&s1[i]!=s2[j])j=nex[j];
if(s1[i]==s2[j]){
j++;
if(j==l2) {puts("yes");return;}
}
}
puts("no");
}
int main()
{
int i,j;
while(scanf("%s%s",s1,s2)!=EOF){
l1=strlen(s1),l2=strlen(s2);
for(i=,j=l1;i<l1;i++,j++) s1[j]=s1[i];
l1*=;
solve();
}
return ;
}
最新文章
- 浩瀚科技 定制现场无线手持打印PDA手持终端扫描条码开单解决方案
- 错误解决:error while loading shared libraries: libcurl.so.4: cannot open shared object file: No such file or directory
- 【BZOJ 2594】【WC 2006】水管局长数据加强版
- mytbatis小问题
- [windows]利用IPSec对指定的ip进行访问限制
- phalcon框架学习之router
- Python抓取页面中超链接(URL)的三中方法比较(HTMLParser、pyquery、正则表达式) <;转>;
- 学习Slim Framework for PHP v3 (七)--route middleware怎么被add进来的?
- java中集合类的简介
- H - Antenna Placement- hdu 3020(二分图匹配)
- fdisk -l 找不到分区怎么办?想办法找到隐藏分区。
- zen-Coding的使用
- 用PHP编写Hadoop的MapReduce程序
- Akka(29): Http:Server-Side-Api,Low-Level-Api
- 分享如何将git项目导入GitHub(附创建分支)
- Exp6 信息搜集与漏洞扫描 20164312 马孝涛
- 使用Dockerfile定制ubuntu+nginx镜像
- Java 并发集合的实现原理
- easyUI中datebox的格式显示
- Android 实践项目开发 总结