[bzoj3507 Cqoi2014]通配符匹配 (hash+DP)

传送门

Solution

显然用哈希233

设\(f[i][j]\)表示第i个通配符和当前第j个字符是否匹配

考虑两种通配符的特性，直接转移即可

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

typedef unsigned long long ull;

const int N=200005,bas=233;

int n,len,tot;

bool f[20][N];

int cl[20];

ull da[N],hs[N],pw[N];

char s[N],ch[N];

int main() {

    pw[0]=1;F(i,1,N-1) pw[i]=pw[i-1]*bas;

    scanf("%s",s+1);len=strlen(s+1);s[++len]='?';

    F(i,1,len) {

        if(s[i]=='*'||s[i]=='?') cl[++tot]=i;

        da[i]=da[i-1]*bas+s[i];

    }

    scanf("%d",&n);

    while(n--) {

        memset(f,0,sizeof(f));f[0][0]=1;

        scanf("%s",ch+1);len=strlen(ch+1);ch[++len]='~';

        F(i,1,len) hs[i]=hs[i-1]*bas+ch[i];

        F(i,0,tot) {

            if(s[cl[i]]=='*') F(j,1,len) f[i][j]|=f[i][j-1];

            F(j,0,len) if(f[i][j]) {

                int l1=cl[i]+1,r1=cl[i+1]-1;

                int l2=j+1,r2=j+cl[i+1]-cl[i]-1;

//              cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;

                if(da[r1]-da[l1-1]*pw[r1-l1+1]!=hs[r2]-hs[l2-1]*pw[r2-l2+1]) continue;

                if(s[cl[i+1]]=='?') f[i+1][r2+1]=1;//,cout<<i+1<<" "<<r2+1<<endl;

                else f[i+1][r2]=1;//,cout<<i+1<<" "<<r2<<endl;

            }

        }

        if(f[tot][len]) puts("YES");

        else puts("NO");

    }

    return 0;

}