首页 > 代码库 > nefu 197 KMP
nefu 197 KMP
Description
在信息检索系统中一个很重要的环节就是关键字符串的查找，从而很多对自己有用的信息。给你一个很长的一段文字, 和一个关键信息字符串，现在要你判断这段文字里面是否有关键字符串。
Input
输入数据有多行，第一行是一个整数n，表示测试实例的个数，后面跟着n行，每行包括一段文字（中间不含空格，长度不超过1000），和一个关键信息字符串（长度不超过10）
Output
输出这段文字里面是否有关键字符串，如果有则输出Yes，否者输入No，具体细节见样例。
Sample Input
3songpanda panhudzpdgj huzaabdcc ad
Sample Output
Case #1: YesCase #2: NoCase #3: No
KMP：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;char str1[1005],str2[1005];int next[1005];void getnext(int L){ int i=0,j=-1; next[0]=-1; while(i<L) { if(j==-1 || str2[j]==str2[i]) { i++; j++; if(str2[i]!=str2[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; }}int kmp(int L1,int L2){ getnext(L2); int i=0,j=0; while(i<L1) { if(j==-1 || str1[i]==str2[j]) i++,j++; else j=next[j]; if(j==L2) return 1; } return 0;}int main(){ int n; int k=0; scanf("%d",&n); getchar(); while(n--) { scanf("%s%s",str1,str2); int ans=kmp(strlen(str1),strlen(str2)); if(ans==1) printf("Case #%d: Yes\n",++k); else printf("Case #%d: No\n",++k); } return 0;}
nefu 197 KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。