2018牛客网暑期ACM多校训练营（第九场）F（AC自动机）

题意

有n(n<=4)个长度为len的字符串，以及一个长度为len2的操作串。每一次你将选取操作串中长度为i（0<=i<=len2）的前缀，问你最少在这个前缀后加多少个字符，使得新字符串的后缀中能够至少出现这n个字符串中的一个。

思路

因为题目中设计多个串的匹配一个长串的问题，我们可以考虑使用AC自动机进行处理。

再考虑题目中要求我们求出匹配串的后缀凑出模式串的最小长度，因此，我们可以将这样的一个问题转化成：在一个Trie图中，处于第i个结点的字符到达任意一个模式串终点j的最短路。

因此，我们只需要利用AC自动机，将利用失配指针的性质，先将整张Trie图建立出来，并将每一个结点到达任意终点的最短路用bfs求出即可。

#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e5+10;
int trie[maxx][26],tot;
int vis[maxx],fail[maxx],ans[maxx];
vector<int>ma[maxx];
void Insert(string s)
{
    int rt=0;
    for(int i=0;i<s.size();i++)
    {
        int id=s[i]-'a';
        if(!trie[rt][id])trie[rt][id]=++tot;
        rt=trie[rt][id];
    }
    vis[rt]=1;
}
void getfail()
{
    queue<int>q;
    for(int i=0;i<26;i++)
        if(trie[0][i])fail[trie[0][i]]=0,q.push(trie[0][i]);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        //如果某个结点的失配指针正好等于某个模式串的终点，则证明该结点也必定跟失配指针所指的结点相同，也可以作为终点处理
        if(vis[fail[u]])vis[u]=1;
        for(int i=0;i<26;i++)
        {
            if(trie[u][i])
            {
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
            }
            else trie[u][i]=trie[fail[u]][i];
        }
    }
}
void bfs() //求每一个结点到达任意终点的最短路
{
    for(int i=0;i<=tot;i++)
        for(int j=0;j<26;j++)
            if(trie[i][j])ma[trie[i][j]].push_back(i);
    queue<int>q;
    for(int i=0;i<=tot;i++)
        if(vis[i])q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<ma[u].size();i++)
        {
            int v=ma[u][i];
            if(vis[v])continue;
            ans[v]=ans[u]+1;
            vis[v]=1;
            q.push(v);
        }
    }
}
void query(string s)
{
    stack<int>st;
    int rt=0;
    printf("%d
",ans[rt]);
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='-'&&st.empty())rt=0;
        else if(s[i]=='-')rt=st.top(),st.pop();
        else st.push(rt),rt=trie[rt][s[i]-'a'];
        printf("%d
",ans[rt]);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    string s;
    for(int i=1;i<=n;i++)
        cin>>s,Insert(s);
    getfail();
    bfs();
    cin>>s;
    query(s);
    return 0;
}