裸地kmp1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define for(i,x,y) for(int i=x;i<=y;i++)
#define D "%d"
#define prf printf
#define scf scanf
char S[199999],T[199999];
int lens,lent;
int Next[199999];
int make_Next(char *T,int m,int *Next)
{
int j=0;
for(i,2,m){
while(j&&T[i]!=T[j+1]) j=Next[j];
if(T[i]==T[j+1]) j++;
Next[i]=j;
}
}
int kmp(char *T,int m,char *S,int n,int *Next)
{
int j=0,ans=0;
for(i,1,n){
while(j&&S[i]!=T[j+1]&&T[j+1]!='?') j=Next[j];
if(S[i]==T[j+1]||T[j+1]=='?') j++;
if(j==m) ans++,j=Next[j];
}
return ans;
}
int n;
int main()
{
freopen("trigger.in","r",stdin);
freopen("trigger.out","w",stdout);
scf(D ,&n);
while(n--)
{
cin>>T>>S;
int i=lent=strlen(T);
int j=lens=strlen(S);
while(i){T[i]=T[i-1];i--;}
while(j){S[j]=S[j-1];j--;}
make_Next(T,lent,Next);
if(kmp(T,lent,S,lens,Next))
prf("God bless You!\n") ;
else prf("Game Over!\n");
}
}