KMP的板子题

给出n组询问,每一组询问包含两个字符串t s,问s中是否包含t。(t中有’?’,’?’可以代替任何字符)。
代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int l1,l2,n;
char s[100009],t[100009];
int nxt[100009];
void next_make()
{
    int t1=0,t2=-1;
    nxt[0]=-1;
    while(t1<l1)
    {
        if(t2==-1||t[t1]==t[t2]||t[t2]=='?') nxt[++t1]=++t2;
        else t2=nxt[t2];
    }
}
void match(int t1,int t2)
{
    while(t1<l1&&t2<l2)
    {
        if(t1==-1||t[t1]==s[t2]||t[t1]=='?') t1++,t2++;
        else t1=nxt[t1];
    }
    if(t1==l1) printf("God bless You!
");
    else printf("Game Over!
");
    return; 
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        cin>>t;cin>>s;
        l1=strlen(t);
        l2=strlen(s);
        next_make();
        match(0,0);
    }
    return 0;
} 
原文地址:https://www.cnblogs.com/dfsac/p/7587892.html