XSY 1004 - 通配符匹配

题目精选 字符串Hash dp

题意

  给定包含通配符 ? 和 * 的字符串 $T$ ，将其与 $S_1,S_2,...,S_n$ 进行匹配，问是否能完全匹配。（匹配的意思是一模一样）
   ? 可以恰好代替一个字符， * 可以代替 $0$ 个以上任意多个的字符。

   $1\le \sum|S|,|T|\le 10^5$
   $通配符个数\le 10$

分析

  设 $f[i][j]$ 表示前 $i$ 个通配符，匹配到 $S$ 的第 $j$ 位是否可行。

  边界： $f[0][0]=1$
  答案： $f[tot][|S|]$ ， $tot$ 为通配符的个数

  转移：每次考虑使用上次的 * ，再将连续的一段进行匹配。于是我们在 $t$ 的末尾补充 ? ，在 $s$ 的末尾补充 # 。

实现

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL unsigned long long
const int N=100000;
const int G=13131;
const int M=15;
LL pwr[N+5];
char t[N+5]; int nt;
LL h[N+5];
int tot;
int loc[M];
int n;
char s[N+5]; int ns;
LL sh[N+5];
int f[M][N+5];
inline int eq(int x,int y,int l,int r) {
    LL hx=(x>y?0:h[y]-h[x-1]*pwr[y-x+1]);
    LL hy=(l>r?0:sh[r]-sh[l-1]*pwr[r-l+1]);
    return hx==hy;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    pwr[0]=1; F(i,1,N) pwr[i]=pwr[i-1]*G;
    scanf("%s",t+1); nt=strlen(t+1); t[++nt]='?';
    F(i,1,nt) h[i]=h[i-1]*G+t[i];
    F(i,1,nt) if (!isalpha(t[i]))
        loc[++tot]=i;
    cin>>n;
    F(c,1,n) {
        scanf("%s",s+1); ns=strlen(s+1); s[++ns]='#';
        F(i,1,ns) sh[i]=sh[i-1]*G+s[i];
        F(i,0,tot) F(j,0,ns) f[i][j]=0; f[0][0]=1;
        F(i,0,tot-1) {
            if (t[loc[i]]=='*')
                F(j,1,ns) f[i][j]|=f[i][j-1];
            F(j,0,ns)
                if (f[i][j]&&eq(loc[i]+1,loc[i+1]-1,j+1,j+loc[i+1]-loc[i]-1)) {
                    if (t[loc[i+1]]=='?')
                        f[i+1][j+loc[i+1]-loc[i]]=1;
                    else f[i+1][j+loc[i+1]-loc[i]-1]=1;
                }
        }
        f[tot][ns]?printf("YES\n"):printf("NO\n");
    }
    return 0;
}