更新时间:2021-07-02 22:53:52
abc a 123456 45 abc ddd
YES YES NO
#include <stdio.h> #include <string.h> int next[1000001]; void Get_next(char str2[]) { int i = 0,j = -1; int len = strlen(str2); next[i] = j; while(i<len) { if(j==-1||str2[i]==str2[j]) { i++; j++; next[i] = j; } else j = next[j]; } } void KMP(char str1[],char str2[]) { Get_next(str2); int i = 0, j = 0; int len1 = strlen(str1), len2 = strlen(str2); while(i<len1&&j<len2) { if(j==-1||str1[i]==str2[j]) { i++; j++; } else j = next[j]; } if(j>=len2) printf("YES\n"); else printf("NO\n"); } int main() { char str1[1000001], str2[1000001]; while(scanf("%s%s",str1,str2)!=EOF) { KMP(str1,str2); } return 0; }