PRoblem Description 给定两个字符串string1和string2，判断string2是否为string1的子串。
Input 输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。(string1和string2大小不超过100字符)
Output 对于每组输入数据，若string2是string1的子串，则输出”YES”，否则输出”NO”。
Example Input
abca12345645abcdddExample Output
YESYESNOHint
Author
#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 1010000using 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; }新闻热点
疑难解答
