数据结构实验之串二:字符串匹配

2/10/2017来源:ASP.NET技巧人气:268

PRoblem Description 给定两个字符串string1和string2,判断string2是否为string1的子串。

Input 输入包含多组数据,每组测试数据包含两行,第一行代表string1,第二行代表string2,string1和string2中保证不出现空格。(string1和string2大小不超过100字符)

Output 对于每组输入数据,若string2是string1的子串,则输出”YES”,否则输出”NO”。

Example Input

abc a 123456 45 abc ddd

Example Output

YES YES NO

Hint

Author

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1010000 using namespace std; void getnext(int *next, char *str, int slen)//第一种next数组 { int i=0, j; next[0]=-1; while(i++<slen) { j=next[i-1]; while(str[j+1]!=str[i]&&j>=0) { j=next[j]; } if(str[j+1]==str[i])next[i]=j+1; else next[i]=-1; } } void getnext1(int *next, char *str, int slen)//另一种,所对应的kmp代码略有不同 { int i=0, j; next[0]=-1; next[1]=0; while(i++<slen) { j=next[i]; while(j>=0&&str[j]!=str[i]) { j=next[j]; } if(j>=0&&str[j]==str[i])next[i+1]=j+1; else next[i+1]=0; } } bool kmp(char *str, int slen, char *ptr , int plen, int *next) { int i=0, j=0; while(i<plen&&j<slen) { if(i>=0&&str[j]==ptr[i]) { i++; j++; } else { if(i<0) { i=0; j++; } else { i=next[i]; } } } if(i==plen)return true; else return false; } int main() { char str[ N ] = {0}; char ptr[ N ] = {0}; int slen, plen; int next[ N ]; while( ~scanf( "%s%s", str, ptr ) ) { slen = strlen( str ); plen = strlen( ptr ); getnext1( next,ptr, plen); if(kmp(str, slen,ptr,plen, next))printf("YES\n"); else printf("NO\n"); } return 0; }