题解：P17214 [ICPC 2017 Nanning R] Banned Patterns

lailai0916 · 2026-08-31 06:17:41 · 题解

题意简述

若一个子串能通过全体大写字母的某个置换变成禁用模式，就称它与该模式匹配。对每个询问字符串，判断它是否包含与任意禁用模式匹配的子串。

解题思路

先把字符串转化成与字母名称无关的形式。依次扫描每个位置，若当前字符此前没有出现，就记为 0；否则记录它与上一次出现位置的距离。例如 ABACB 的编码为 0 0 2 0 3。

两个等长字符串能够通过字母置换互相转化，当且仅当它们的编码相同。

先看必要性。字母置换不会改变任意两个位置上的字符是否相同。因此，每个位置的上一次相同字符位置不变，编码也不变。

再看充分性。编码为 0 的位置依次建立新的字符类。编码非零的位置则指向同类字符的上一次出现。编码相同意味着两个字符串具有完全相同的字符分类。将对应的字符类一一映射，即可补成一个大写字母置换。

把所有禁用模式的距离编码插入 Trie。同一个询问位置放入不同长度的后缀时，其编码可能不同。因此，不能直接使用普通 AC 自动机的字符转移。

设当前 Trie 状态的深度为 d，询问中新字符与上一个相同字符的全局距离为 e。若 1\le e\le d，上一次出现仍在当前后缀内，局部编码就是 e。否则，上一次出现位于后缀之外，局部编码应改为 0。本次真正使用的边权为：

定义 go(u,e) 表示从状态 u 读入全局距离 e。先根据 u 的深度计算局部边权 c。若不存在对应的儿子，就跳到失配指针。随后按照新状态的深度重新计算 c，到达根或找到儿子时结束。

这里必须在每次失配后重新计算。原状态可能满足 e\le d，但较短的后缀可能不再包含上一次出现位置。此时同一个字符的局部编码会从 e 变成 0。

接下来构造失配指针。设 Trie 边 u\to v 的边权为 e。这条边权是对应模式前缀中新字符的全局前驱距离。从 fail_u 出发调用 go(fail_u,e)，得到的正是 v 所代表字符串的最长可匹配真后缀。因此：

按照深度递增的 BFS 顺序计算。若 fail_u 对应的后缀定义成立，go 会逐一检查更短的可匹配后缀。它还会按各自长度修正新字符编码，所以所得状态仍满足定义。由归纳可知，全部失配指针都正确。

若节点本身是某个禁用模式的结尾，或者其失配指针指向禁用结尾，就把该节点标记为禁用。扫描询问时，当前状态始终是已读前缀的最长可匹配后缀。一旦进入禁用状态，就已经找到一个匹配子串。

一个 Trie 节点最多有 27 个儿子。追加字符时，它要么形成新字符类，对应边权 0；要么等于已有至多 26 个字符类之一。后者由该类最后一次出现的位置唯一确定边权。将出边排序后，可以二分查找。

在扫描一条字符串时，成功转移只让状态深度增加 1，每次失配都会降低深度。因此，全部失配次数是线性的。构造失配指针时，也可以沿每条输入模式作相同的深度增减计费。

设模式总长为 S，询问总长为 L。时间复杂度为 O((S+L)\log 26)，空间复杂度为 O(S)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=100005;
vector<pii> g[N];
int fail[N],dep[N];
bool bad[N];
int tot;
int get(int u,int c)
{
    auto it=lower_bound(g[u].begin(),g[u].end(),pii(c,0));
    if(it==g[u].end()||it->first!=c)return -1;
    return it->second;
}
int add(int u,int c)
{
    for(auto [d,v]:g[u])
    {
        if(d==c)return v;
    }
    int v=++tot;
    dep[v]=dep[u]+1;
    g[u].push_back({c,v});
    return v;
}
int go(int u,int d)
{
    while(1)
    {
        int c=d<=dep[u]?d:0;
        int v=get(u,c);
        if(v!=-1)return v;
        if(!u)return 0;
        u=fail[u];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    for(int k=1;k<=t;k++)
    {
        int n;
        cin>>n;
        tot=0;
        while(n--)
        {
            string s;
            cin>>s;
            int last[26]={};
            int u=0,pos=0;
            for(char v:s)
            {
                int c=v-'A';
                pos++;
                int d=last[c]?pos-last[c]:0;
                last[c]=pos;
                u=add(u,d);
            }
            bad[u]=1;
        }
        for(int i=0;i<=tot;i++)sort(g[i].begin(),g[i].end());
        queue<int> q;
        for(auto [d,v]:g[0])
        {
            fail[v]=0;
            q.push(v);
        }
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            bad[u]=bad[u]||bad[fail[u]];
            for(auto [d,v]:g[u])
            {
                fail[v]=go(fail[u],d);
                q.push(v);
            }
        }
        int m;
        cin>>m;
        cout<<"Case #"<<k<<':';
        while(m--)
        {
            string s;
            cin>>s;
            int last[26]={};
            int u=0,pos=0;
            bool flag=0;
            for(char v:s)
            {
                int c=v-'A';
                pos++;
                int d=last[c]?pos-last[c]:0;
                last[c]=pos;
                u=go(u,d);
                if(bad[u])
                {
                    flag=1;
                    break;
                }
            }
            cout<<' '<<(flag?'Y':'N');
        }
        cout<<'\n';
        for(int i=0;i<=tot;i++)
        {
            g[i].clear();
            fail[i]=dep[i]=0;
            bad[i]=0;
        }
    }
    return 0;
}