首页 > 代码库 > 数据结构之 字符串---字符串匹配（kmp算法）
数据结构之 字符串---字符串匹配（kmp算法）
串结构练习——字符串匹配
Time Limit: 1000MS Memory limit: 65536K
题目描述
给定两个字符串string1和string2，判断string2是否为string1的子串。
输入
输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。
输出
对于每组输入数据，若string2是string1的子串，则输出"YES"，否则输出"NO"。
示例输入
abca12345645abcddd
示例输出
YESYESNO
#include <iostream>#include <string>#include <cstdio>#include <cstring>#include <algorithm>#include <stack>using namespace std;void GET_next(string t, int next[]){ int j, k; j=0; k=-1; next[0]=-1; int len=t.size(); while(j<len ) { if(k==-1 || t[j]==t[k] ) { j++; k++; next[j]=k; } else k=next[k]; }}int KMP(string s, string t, int next[] ){ int i, j; i=0; j=0; int len1=s.size(); int len2=t.size(); while(i<len1 && j<len2 ) { if(j==-1 || s[i]==t[j] ) { i++; j++; } else j=next[j]; } if(j==len2 ) cout<<"YES\n"; else cout<<"NO\n"; return 0;}int main(){ string s, t; int i, j; int len1, len2; int next[1000]; while(cin>>s) { cin>>t; len1=s.size(); len2=t.size(); GET_next(t, next); KMP(s, t, next); } return 0;}
数据结构之 字符串---字符串匹配（kmp算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。