zcmimi's blog

查看原题

点击跳转

f[i][j]表示用完前i个通配符,是否能匹配[1,j],

s为含通配符字符串,t为目标字符串,p_i为第i个通配符的位置

下文x|=y表示: 若y能,则x也能

若第i个通配符为*,*可以代替j之后的所有字符

那么f[i][j]|=f[i][j-1],也就是用*继续匹配下去(j-1位之后用*匹配)

s[p_i+1,p_{i+1}-1]=t[j+1,j+p_{i+1}-p_i-1],

那么f[i+1][j+(p_{i+1}-1)-(p_i+1)+1+[s[p_{i+1}]=?]]|=1

其中[s[p_{i+1}]='?']s[p_{i+1}]?时为1,否则为0

详见代码

#include<bits/stdc++.h>
typedef unsigned long long ull;
const int N=100011,bs=131;
char s[N],t[N];
ull S[N],T[N],pw[N];
void hs(ull*H,char*s){
    int n=strlen(s+1);
    for(int i=1;i<=n;++i)H[i]=H[i-1]*bs+(ull)s[i];
}
ull gh(ull*H,int l,int r){
    if(r<l)return -1;
    return H[r]-H[l-1]*pw[r-l+1];
}
int cnt,p[N];
bool f[15][N];
void solve(){
    int n=strlen(t+1);t[++n]='&';
    hs(T,t);
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=0;i<=cnt;++i){
        if(s[p[i]]=='*')
            for(int j=1;j<=n;++j)
                f[i][j]|=f[i][j-1];//这一位用*继续匹配
        for(int j=0;j<=n;++j)
            if(f[i][j]&&gh(T,j+1,j+(p[i+1]-1)-(p[i]+1)+1)==gh(S,p[i]+1,p[i+1]-1))
                f[i+1][j+(p[i+1]-1)-(p[i]+1)+1+(s[p[i+1]]=='?')]|=1;
    }
    puts(f[cnt][n]?"YES":"NO");
}
int main(){
    pw[0]=1;
    for(int i=1;i<=100000;++i)pw[i]=pw[i-1]*bs;
    scanf("%s",s+1);
    int n=strlen(s+1),m;
    for(int i=1;i<=n;++i)if(s[i]=='*'||s[i]=='?')p[++cnt]=i;
    s[p[++cnt]=++n]='?';
    hs(S,s);
    scanf("%d",&m);
    while(m--)scanf("%s",t+1),solve();
}
LG 3167 [CQOI2014]通配符匹配
comment评论
Search
search