洛谷 P3167 分析（别看）

科技起源的小号1

2026-10-11 11:56:54

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：求若干组询问的可行性

1.2 题目背景、允许、禁止与限制

背景：给定一个模板字符串和 $n$ 个匹配字符串（匹配字符串均为小写字母，模板字符串除符号外同样均为小写字母）
允许：模板字符串有三种符号，分别为字母，?和*
对于每个匹配字符串，检查其是否与模板字符串相等
相等的条件：将模板字符串中的?替换成任意 $1$ 个小写字母，将*替换成任意 $[0,\infty)$ 个小写字母后模板字符串和匹配字符串完全相等

1.3 题目数据范围与猜测

$1 \le n \le 100,字符串长度 \le 100000 \longrightarrow O(n|s|)$
$通配符的个数不超过10 \to$ 非常重要的点

1.4 一句话概括题意

给定模板字符串和若干询问字符串，检查每个询问字符串能否通过模板字符串中字符的替换得到

2 题目破题推导

2.1 第一步：大拆小，小组大

观察到很重要的点： $通配符的个数不超过10$
考虑按通配符的位置将模板字符串分割成若干段

2.2 第二步：正向思维转逆向思维

正向思维：直接拿模板去匹配询问字符串
逆向思维：用“段”去匹配。定义 $dp[i][j]$ 表示“模板的前 $i$ 段，能否匹配目标字符串的前 $j$ 个字符”

2.3 第三步：分情况讨论

对于第 $i$ 段，有两种情况

第 $i$ 段后面是一个?
因为?只能匹配一个字符，所以转移 $dp[i+1][j+第i段区间长度+1]$ 是可行的
第 $i$ 段后面是一个*
因为*可以匹配 $[0,\infty)$ 个字符
那么转移 $dp[i+1][j+第i段区间长度]$ 可行，此时代表我不使用*匹配字符
同时因为*可“吞”很多字符，因此如果此时 $dp[i][j-1]$ 可行，则 $dp[i][j]$ 也可行

2.4 第四步：优化

判断“段”能否匹配某一区间，需要 $O(段长度)$ 的时间，这样会超时，所以用 $\huge{字符串hash}$

3 模型匹配

上面已经讲述
dp是可以设置成bool类型的！

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n;
const int N = 111111, M = 15, K = 2;
char t[N], s[N];
bool dp[M][N];
int loc[M];
ull p[N], hsh[N][K];
ull base = 131;
int cnt;

void dohash(char *s, int k){
    int len = strlen(s + 1);
    hsh[0][k] = 0;
    for (int i = 1;i <= len;i++){
        hsh[i][k] = hsh[i - 1][k] * base + (ull)s[i];    
    }
}
ull gethash(int l, int r, int k){
    if (r < l) return -1;
    return hsh[r][k] - p[r - l + 1] * hsh[l - 1][k];
}

int main(){

    scanf("%s", t + 1);
    int Len = strlen(t + 1);
    p[0] = 1;
    for (int i = 1;i <= 100001;i++){
        p[i] = p[i - 1] * base;
    }
    dohash(t, 0);
    for (int i = 1;i <= Len;i++){
        if (t[i] == '?' || t[i] == '*'){
            loc[++cnt] = i;
        }
    }
    Len++;
    loc[++cnt] = Len;
    t[Len] = '?';
    cin >> n;
    while(n--){
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        s[++len] = '&';
        dohash(s, 1);
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for (int i = 0;i <= cnt;i++){
            if (t[loc[i]] == '*'){
                for (int j = 1;j <= len;j++){
                    if (dp[i][j - 1]){
                        dp[i][j] = true;
                    }
                }
            }
            int left = loc[i] + 1, right = loc[i + 1] - 1;
            int seg = right - left + 1;
            for (int j = 0;j <= len;j++){
                if (dp[i][j] && gethash(left, right , 0) == gethash(j + 1, j + seg, 1)){
                    if (t[loc[i + 1]] == '?'){
                        dp[i + 1][j + seg + 1] = true;
                    } else {
                        dp[i + 1][j + seg] = true;
                    }
                }
            }
        }
        cout << (dp[cnt][len] ? "YES" : "NO") << endl;
    }
    
    return 0;   
}