题解：P3883 [JLOI2008] 棋局定式

· · 题解

题意简述

现在有一盘棋局，棋局中的每一步都可以用一个长度不超过 4 的字符串来表示，我们可以通过拼接将其视为一个字符串；此外棋局中还有 n 个定式，每个定式也由 k 个长度不超过 4 的字符串拼接，我们同样可以拼接视为一个字符串；问在这盘棋局中出现了那些定式，以及有多少个定式的字符串成为了棋局字符串的子串，按顺序输出定式的名称。

思路讲解

本题只要我们将那些短字符串拼接成若干个长字符串后，那么实际上这就是一个多模式串匹配文本串的题，这种题我们通常使用 AC 自动机来完成，如果我们直接将每个字符压入到 Trie 树上时，那么其字符集大小就变成了 120。（120 即小写字符 x 的 ascll 值），这个字符集在 \sum k=200000 的情况下是有可能超时的，我们考虑实际上用到的字符只有 23 个，因此我们给其编一个号即可大幅缩小字符集的大小。对于每一个定式压入 Trie 树后，我们需要记录每个字符串的末尾字符对应其上面的哪一个节点，这样做，在后面查询的过程中我们只需要标记我们走过 AC 自动机的哪些节点，如果哪些定式对应的节点被标记，就代表当前定式完全出现了一次，直接输出当前定式的名字即可。

此外，在 AC 自动机查询的时候有一个小剪枝，当遇到了已经被标记过的节点，说明它与它的 fail 树上的儿子均都被标记，那我们直接返回即可，这样做法时间复杂度是线性的，总时间复杂度为 O(L+M)。

特别提醒

本题中对于 k 的读入尽量不要用普通快读，最好普通读入一个 k，这样会残留一个换行符，再读入两次字符串即可，读入换行的差异问题很致命！！！！

代码时间

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
typedef long long ll;
const int N=1e6+5;

inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n,m,cnt,idx,ans[N];
bool vis[N];
string a[N],t;
map<char,int> mp;
struct KK{
    int son[27];
    int fail;
}tr[N];

void ycl(){
    mp['K']=++cnt,mp['Q']=++cnt,mp['B']=++cnt,mp['N']=++cnt,mp['R']=++cnt,mp['P']=++cnt;
    for(int i='1';i<='8';i++) mp[i]=++cnt;
    for(int i='a';i<='h';i++) mp[i]=++cnt; 
    mp['x']=++cnt;
}

void add(string ss,int id){
    int now=0;
    for(int i=0;i<(int)ss.size();i++){
        int v=tr[now].son[mp[ss[i]]];
        if(!v) v=++idx,tr[now].son[mp[ss[i]]]=v;
        now=v;
    }
    ans[id]=now;
}

void build_AC(){
    queue<int> q;
    for(int i=0;i<26;i++) if(tr[0].son[i]) q.push(tr[0].son[i]);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(tr[x].son[i]){
                tr[tr[x].son[i]].fail=tr[tr[x].fail].son[i];
                q.push(tr[x].son[i]);
            }else{
                tr[x].son[i]=tr[tr[x].fail].son[i];
            }
        }
    }
}

void ask(string ss){
    int now=0;
    for(int i=0;i<(int)ss.size();i++){
        now=tr[now].son[mp[ss[i]]];
        for(int j=now;j;j=tr[j].fail){
            if(vis[j]) break;
            vis[j]=1;
        }
    }
}

int main(){
    // freopen("1.in","r",stdin);

    ycl();

    n=read(),m=read();
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        getline(cin,a[i]);// 碎碎念：因为这个问题我和同学足足调了快一个小时！！！
        getline(cin,a[i]);
        string ss="";
        for(int j=1;j<=k;j++){
            cin>>t;
            ss+=t;
        }
        add(ss,i);
    }
    string ss="";
    for(int i=1;i<=m;i++){
        cin>>t;
        ss+=t;
    }

    build_AC();
    ask(ss);

    for(int i=1;i<=n;i++){
        if(vis[ans[i]]) cout<<a[i]<<endl;
    }
    return 0;
}
//code submission time--- 5.12 --- P3883 [JLOI2008] 棋局定式

感谢阅读，谢谢喵\~\~\~