题意：给定一篇文章和一些句子。询问句子是否在文章中出现。
kmp模板题
/*
kmp
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int maxm = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-; char text[ maxn ][ maxm ];
int len_text;
char pat[ maxn ][ maxm ];
int len_pat;
int next[ maxn ]; void getnext(){
int i,j;
next[ ] = -;
i = ;
j = -;
while( i<len_pat ){
if( j==-||strcmp( pat[i],pat[j] )==||strcmp( pat[j],"_" )==||strcmp( pat[i],"_" )== ){
i ++ ;
j ++ ;
next[ i ] = j;
}
else
j = next[ j ];
}
return ;
} bool kmp( ){
getnext();
//for( int i=0;i<len_pat;i++ ){
// printf("next[ %d ] = %d \n",i,next[i]);
//}
int i,j;
i = ;
j = ;
while( i<len_text&&j<len_pat ){
if( j==-||strcmp( text[i],pat[j] )==||strcmp(pat[j],"_")== ){
i ++ ;
j ++ ;
}
else
j = next[j];
if( j==len_pat ) return true;
}
return false;
} int main(){
int T;
scanf("%d",&T);
int Case = ;
while( T-- ){
len_text = ;
while( ){
scanf("%s",text[ len_text ]);
if( strcmp( text[ len_text ],"@" )== ){
break;
}
len_text ++ ;
}//input the passage
int m;
scanf("%d",&m);
printf("Case %d:\n",Case++);
while( m-- ){
len_pat = ;
while( ){
scanf("%s",pat[ len_pat ]);
if( strcmp( pat[ len_pat ],"@" )== ){
break;
}
len_pat ++ ;
}
bool flag = kmp();
if( flag ) puts("YES");
else puts("NO");
}
}
return ;
}