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; }新聞熱點
疑難解答
