洛谷3167 [CQOI2014]通配符匹配

Luogu

LOJ

分析

设 $dp_{i,j}$ 表示前 $i$ 个通配符能否匹配前 $j$ 个字符。

考虑怎么转移。显然我们需要比较两个串是否相等,这个利用 hash 判断即可。

转移 * 的情况时需要一些奇妙的姿势保证复杂度正确。

另外最好在模板串末尾加一个 ? ,在匹配串末尾加一个任意未出现字符,便于 DP。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef unsigned long long ull;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int BASE=19260817;

int la,lb,tot=0,s[N];
char a[N],b[N];
ull pw[N],ha[N],hb[N];
int dp[20][N];

inline ull getha(int l,int r) { return ha[r]-pw[r-l+1]*ha[l-1]; }
inline ull gethb(int l,int r) { return hb[r]-pw[r-l+1]*hb[l-1]; }

int main() {
    pw[0]=1;
    for (re int i=1;i<N;++i) pw[i]=pw[i-1]*BASE;
    scanf("%s",a+1),la=strlen(a+1)+1,a[la]='?';
    for (re int i=1;i<=la;++i) ha[i]=ha[i-1]*BASE+a[i];
    for (re int i=1;i<=la;++i) if (!isalpha(a[i])) s[++tot]=i;
    for (int T=read();T;--T) {
        scanf("%s",b+1),lb=strlen(b+1)+1,b[lb]='%';
        for (re int i=1;i<=lb;++i) hb[i]=hb[i-1]*BASE+b[i];
        memset(dp,0,sizeof(dp)),dp[0][0]=1;
        for (re int i=0;i<=tot;++i) {
            if (a[s[i]]=='*')
                for (re int j=1;j<=lb;++j) dp[i][j]|=dp[i][j-1];
            for (re int j=0;j<=lb;++j) {
                if (!dp[i][j]) continue;
                int la=s[i]+1,ra=s[i+1]-1,lb=j+1,rb=j+1+(ra-la);
                if (getha(la,ra)!=gethb(lb,rb)) continue;
                if (a[s[i+1]]=='?') dp[i+1][rb+1]|=dp[i][j];
                else dp[i+1][rb]|=dp[i][j];
            }
        }
        puts(dp[tot][lb]?"YES":"NO");
    }
    return 0;
}
最后修改:2019 年 10 月 06 日 03 : 16 PM

发表评论