Chlience

【题解】BZOJ 3507 [CQOI2014]通配符匹配
Problem给定含有 '?' 和 '*' 的模板串以及 $n$ 个模式串,问是否能够匹配Thought首先考虑只...
扫描右侧二维码阅读全文
20
2018/12

【题解】BZOJ 3507 [CQOI2014]通配符匹配

Problem

给定含有 '?' 和 '*' 的模板串以及 $n$ 个模式串,问是否能够匹配

Thought

首先考虑只有 '?' 的情况

设 $f[i][j]$ 表示模式串第 $i$ 个字符匹配到了第 $j$ 个 '?'
显然,如果 $f[i][j]=1$,则 $f[i+1][j],\cdots,f[n][j]=1$

那么就可以在 $i$ 打上一个标记表示能够其后面位置都能匹配到第 $j$ 个 '?'
每次只用从 $f[i][j]$ 判断一下模板串第 $j$ 到第 $j+1$ 个串之间的位置能否和模式串 $i+1$ 之后的串匹配即可转移

考虑加入 ‘*’ 的情况,因为其必然需要匹配一个字符,那么只能确定某个特定的位置进行转移,存下即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 100010;
char s[N];
int len , nowl;
ll w[N] , now;
ll ns[N];
ll pos[N];
int opt[N] , num , l[N];
bool f[N][20];
bool match[20];
void check_match(int x) {
    for(int i = 1 ; i <= num ; ++ i)
        if(f[x][i] == 1 && !opt[i])
            match[i] = 1;
}
bool get(int x , int y) {
    if(!x && !y) return 1;
    if(!opt[y])
        return f[x][y] || match[y];
    else
        return f[x][y];
}
int main() {
    scanf("%s" , s + 1);
    len = strlen(s + 1);
    s[++ len] = '?';
    for(int i = 1 ; i <= len ; ++ i) {
        if(s[i] == '*' || s[i] == '?') {
            ++ num;
            opt[num] = s[i] == '?';
            w[num] = now;
            l[num] = nowl;
            now = 0;
            nowl = 0;
        }
        else {
            now = now * 131 + s[i] - 'a' + 1;
            nowl ++;
        }
    }
    int n;
    scanf("%d" , &n);
    pos[0] = 1;
    for(int i = 1 ; i < N ; ++ i) pos[i] = pos[i - 1] * 131;
    while(n --) {
        scanf("%s" , s + 1);
        len = strlen(s + 1);
        s[++ len] = '$';
        for(int i = 1 ; i <= len ; ++ i)
            ns[i] = ns[i - 1] * 131 + s[i] - 'a' + 1;
        for(int i = 0 ; i < len ; ++ i) {
            for(int j = 0 ; j < num ; ++ j) {
                if(get(i , j)) {
                    if(opt[j + 1] == 1) {
                        if(i + l[j + 1] < len && ns[i + l[j + 1]] - ns[i] * pos[l[j + 1]] == w[j + 1])
                            f[i + l[j + 1] + 1][j + 1] = 1;
                    }
                    else {
                        if(i + l[j + 1] <= len && ns[i + l[j + 1]] - ns[i] * pos[l[j + 1]] == w[j + 1])
                            f[i + l[j + 1]][j + 1] = 1;
                    }
                }
            }
            check_match(i);
        }
        if(f[len][num]) puts("YES");
        else puts("NO");
        for(int i = 0 ; i <= len ; ++ i)
            for(int j = 0 ; j <= num ; ++ j)
                f[i][j] = 0;
        memset(match , 0 , sizeof(match));
    }
    return 0;
}
Last modification:December 21st, 2018 at 09:00 pm

Leave a Comment