题目理解

我们有一个文本串 $s$ 和多个模式串 $p_i$，但匹配规则特殊：

两个字符串相等的条件：

1. 长度相等
2. 所有不匹配字符的位置距离 $< k$
3. 如果长度 $\le k$，则直接认为相等

---

核心转化

1. 特殊匹配规则的意义

条件2意味着：所有不匹配的字符位置必须聚集在一个长度 $< k$ 的区间内。

换句话说：如果我们在模式串和文本串的某个子串中，找到第一个不匹配的位置 $i$ 和最后一个不匹配的位置 $j$，那么必须有 $j-i < k$。

---

算法思路

2. 关键观察

对于模式串 $p$ 在文本串 $s$ 中的一次出现（起始位置 $pos$），考虑将 $p$ 分成两部分：

• 前缀 $p[1 \dots i]$ 完全匹配
• 后缀 $p[j \dots |p|]$ 完全匹配
• 中间 $p[i+1 \dots j-1]$ 可能不匹配

由于不匹配位置距离 $< k$，所以 $j-i \le k$。

---

3. 算法框架

代码使用了 双向AC自动机 的技术：

• 正向AC自动机：处理前缀匹配
• 反向AC自动机：处理后缀匹配
• 然后通过 树状数组 + DFS序 统计满足条件的匹配

---

代码结构解析

4. 数据结构定义

struct ACAM {
    int ch[maxs << 1][sig], fail[maxs << 1], tot;
    // AC自动机基本结构
};

• ch：Trie树转移
• fail：AC自动机的fail指针
• tot：节点计数

---

5. 模式串预处理

void insert(int st, int len, int id) {
    // 正向插入
    int cur = 0;
    rep(v1, st, st + len - 1) {
        if (!ch[cur][ap[v1] - 33]) 
            ch[cur][ap[v1] - 33] = ++tot;
        cur = ch[cur][ap[v1] - 33];
        prk[v1][0] = cur;  // 记录每个位置的正向状态
    }
    
    // 反向插入  
    cur = 0;
    per(v1, st + len - 1, st) {
        if (!ch[cur][ap[v1] - 33])
            ch[cur][ap[v1] - 33] = ++tot;
        cur = ch[cur][ap[v1] - 33];
        prk[v1][1] = cur;  // 记录每个位置的反向状态
    }
}

这里为每个模式串同时构建了正向和反向的Trie路径。

---

6. 查询条件构建

rep(v1, st - 1, st + len - ik - 1) {
    Ask[prk[v1][0]][0].push_back(make_pair(prk[v1 + ik + 1][1], id));
    if (v1 >= st)
        Ask[prk[v1][0]][1].push_back(make_pair(prk[v1 + ik][1], id));
}

这部分的逻辑是：枚举所有可能的分割点，记录"前缀匹配到状态X且后缀匹配到状态Y"的查询条件。

---

7. AC自动机构建

标准的AC自动机构建，同时建立fail树：

void build() {
    rep(v1, 0, sig - 1) if (ch[0][v1]) 
        q.push(ch[0][v1]);
    
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        T[fail[cur]].push_back(cur);  // 建立fail树
        rep(v1, 0, sig - 1) {
            if (ch[cur][v1]) {
                fail[ch[cur][v1]] = ch[fail[cur]][v1];
                q.push(ch[cur][v1]);
            } else {
                ch[cur][v1] = ch[fail[cur]][v1];
            }
        }
    }
}

---

8. 文本串匹配

void walk(int len) {
    // 正向匹配
    int cur = 0;
    rep(v1, 1, len) {
        cur = ch[cur][s[v1] - 33];
        lnk[v1][0] = cur;  // 记录每个位置的正向状态
    }
    
    // 反向匹配
    cur = 0;
    per(v1, len, 1) {
        cur = ch[cur][s[v1] - 33];
        lnk[v1][1] = cur;  // 记录每个位置的反向状态
    }
}

---

9. 核心统计：DFS + 树状数组

void dfs(int cur, int p) {
    // 处理查询：进入节点时记录当前值
    for (pr v : Ask[cur][p]) {
        ans[v.second] += query_sub(v.first) * mp[!p];
    }
    
    // 递归子节点
    for (int v : T[cur]) {
        dfs(v, p);
    }
    
    // 添加当前节点的贡献
    for (int v : Mod[cur][p]) {
        modify(dfn[v], 1);
    }
    
    // 再次处理查询：计算增量
    for (pr v : Ask[cur][p]) {
        ans[v.second] += query_sub(v.first) * mp[p];
    }
}

这个DFS实现了 树上差分 的效果：

• 第一次查询得到进入节点时的值
• 添加当前节点的贡献
• 第二次查询得到离开节点时的值
• 差值就是在当前节点子树中新增的匹配数

---

10. 树状数组维护

void modify(int pos, int v) {
    for (int v1 = pos; v1 <= dfn_cnt; v1 += v1 & (-v1))
        sum[v1] += v;
}

int query_sub(int x) {
    return query_pre(dfn[x] + siz[x] - 1) - query_pre(dfn[x] - 1);
}

树状数组用于快速查询一个节点的子树和。

---

算法流程总结

1. 构建双向AC自动机：为所有模式串建立正向和反向Trie
2. 建立fail树：获得DFS序，便于子树操作
3. 文本串匹配：记录每个位置的正向和反向状态
4. 树上统计：通过DFS在fail树上统计满足条件的匹配
5. 特殊处理：长度 $\le k$ 的模式串直接计算

---

复杂度分析

• AC自动机构建：$O(\sum |p_i| \times \Sigma)$
• 文本串匹配：$O(|s|)$
• 树上统计：$O((|s| + \sum |p_i|) \log n)$
• 总复杂度：$O((|s| + \sum |p_i|) \log n)$，在数据范围内可接受

---

样例验证

对于样例：

k=1, s="xyz"
p1="xz", p2="y", p3="xzy"

• p1="xz"：可以与"xy"、"yz"匹配（各有一个位置不同，距离=0<1）
• p2="y"：可以与"x"、"y"、"z"匹配（长度=1≤1）
• p3="xzy"：无法匹配（有两个位置不同，距离=1不<1）

输出2, 3, 0符合样例。

---

总结

这道题综合运用了：

1. AC自动机：多模式匹配
2. 双向匹配：处理带容错的匹配
3. 树状数组：快速子树查询
4. DFS序：将子树操作转化为区间操作
5. 树上差分：高效统计匹配数

是字符串匹配问题中非常复杂和精巧的解法。