kmp算法题目，如图，求解答

来源：蜘蛛抓取(WebSpider) 时间：2016-10-02 15:39 标签： kmp算法详解
1499人阅读
ACM____数据结构（63）
& & & & & & & & & & & & & & & & & & & & & & 链接：
Problem Description
Sample Input
Sample Output
参考了下面这三位大牛的KMP 的讲解，收获多多。
#include &queue&
#include &cmath&
#include &cstdio&
#include &string&
#include &cstring&
#include &iostream&
#include &algorithm&
#define FIN
freopen(&input.txt&,&r&,stdin)
#define FOUT
freopen(&output.txt&,&w&,stdout)
#define UFOR(i,a,b)
for(int i =i &=i++)
#define CASE(T)
int T;for(scanf(&%d&,&T);T--;)
//typedef __int64
//typedef long long LL;
const double eps = 1e-10;
const int maxn = 1000+5;
char s[maxn],p[maxn];
int Next[maxn];
void getNext(const char x[],int len)
j = Next[0] = -1;
while(i & len)
while(-1 != j &&
x[i] != x[j]) j = Next[j];
if(x[i] == x[j]) Next[i] = Next[j];
else Next[i] =
int KMP(const char p[],int plen,const char s[],int slen)
int ans = 0;
getNext(p,plen);
i = j = 0;
while(i & slen)
while(-1 != j && s[i] != p[j]) j = Next[j];
if(j &= plen)
int main()
#ifndef ONLINE_JUDGE
#endif // ONLINE_JUDGE
while(~scanf(&%s&,s))
if(s[0] == '#')
scanf(&%s&,p);
int ans = KMP(p,strlen(p),s,strlen(s));
printf(&%d\n&,ans);
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &链接：
Problem Description
Sample Input
Sample Output
给定字符串a,b,输出两个字符串连接起来的最小字典序，有个条件，如果字符串s1的某个前缀与s2的某个后缀相同，那么可以把前缀和后缀合并起来，也就是是要输出前缀或者后缀中的一个即可。
#include &cmath&
#include &cstdio&
#include &string&
#include &cstring&
#include &iostream&
#include &algorithm&
#define FIN
freopen(&input.txt&,&r&,stdin)
#define FOUT
freopen(&output.txt&,&w&,stdout)
#define CASE(T)
int T;for(scanf(&%d&,&T);T--;)
const int maxn = ;
char a[maxn],b[maxn];
int Next[maxn];
void getNext(char x[],int m,int next[])
j = next[0] = -1, i = 0;
while(i & m)
while(-1 != j && x[i] != x[j]) j = next[j];
if(x[i] == x[j]) next[i] = next[j];
else next[i] =
int KMP(char s[],int slen,char p[],int plen)
int i,j,ans = 0;
getNext(p,plen,Next);
i = j = 0;
while(i & slen)
while(-1 != j && s[i] != p[j]) j = Next[j];
return (j == -1) ? 0 :
int main()
#ifndef ONLINE_JUDGE
#endif // ONLINE_JUDGE
while(~scanf(&%s %s&,a,b))
int lab = 0,lba = 0,t;
int alen = strlen(a), blen = strlen(b);
t = min(alen,blen);
lab = KMP(a,alen,b,blen);
lba = KMP(b,blen,a,alen);
if(lab & lba)
a[alen-lab] = '\0';
printf(&%s%s\n&,a,b);
else if(lab & lba)
b[blen-lba] = '\0';
printf(&%s%s\n&,b,a);
else if(lab == 0)
string str1(a);str1 +=
string str2(b);str2 +=
printf(&%s\n&,min(str1,str2).c_str());
t1 = a[alen-lab];
a[alen-lab] = '\0';
string str1(a);
a[alen-lab] = t1;
b[blen-lba] = '\0';
string str2(b);
printf(&%s\n&,min(str1,str2).c_str());
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：137720次
积分：3872
积分：3872
排名：第6630名
原创：225篇
转载：10篇
评论：25条
(24)(14)(13)(16)(21)(46)(28)(2)(2)(3)(1)(1)(2)(2)(33)(21)(6)(1)2011年9月 C/C++大版内专家分月排行榜第二2011年4月 C/C++大版内专家分月排行榜第二2010年11月 C/C++大版内专家分月排行榜第二
2011年6月 C/C++大版内专家分月排行榜第三
2011年9月 C/C++大版内专家分月排行榜第二2011年4月 C/C++大版内专家分月排行榜第二2010年11月 C/C++大版内专家分月排行榜第二
2011年6月 C/C++大版内专家分月排行榜第三
2011年9月 C/C++大版内专家分月排行榜第二2011年4月 C/C++大版内专家分月排行榜第二2010年11月 C/C++大版内专家分月排行榜第二
2011年6月 C/C++大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。第七章 图习题解答(1)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第七章 图习题解答(1)
上传于||文档简介
&&数据结构 清华大学出版社 习题答案
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩2页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢我们都应该掌握的算法经典问题_一天一道算法题_传送门
你是真实用户吗(Are you a robot)?
我们怀疑你不是真实用户，已对你的访问做了限制。如果您是真实用户，非常抱歉我们的误判对您造成的影响，您可以通过QQ()或电子邮件()反馈给我们，并在邮件和QQ请求信息里注明您的IP地址：220.177.198.53，我们会尽快恢复您的正常访问权限。另外，如果您不是在访问的当前页面，我们建议您移步
或者 在浏览器中输入以下地址：http://chuansong.me/n/449080 访问，您所访问的网站是从抓取的数据，请直接访问，会有更好的体验和更及时的更新。We suspect you are a robot.We are really sorry if you are not,and you can email us () with your current IP address: 220.177.198.53 to get full access to .If you are not accessing
for the current page,you'd better visit
for better performance,as the current website you are accessing is just spam.

我要回帖

更多关于 kmp算法详解 的文章

 

随机推荐