AC自动机

AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的。
@[toc]

解决：多模式匹配问题

匹配问题：
有多个不同的模式串s[1...N]
给定长度=M的目标串t，求每个模式串s[i]总共在t中出现了多少次
跑N遍kmp

字典树：

对所有的模式串s[1...N]构建trie
字典树的根到字典树上任意节点构成的路径都对应某个模式串s[i]的前缀
概念：
状态：对字典树的任何一个结点都看做状态，对应某个模式串s[i]的前缀
转移：任意一个状态添加一个字符得到新状态
可识别：字符串能对应上字典树上的一个状态
在这里插入图片描述
"the"为可识别状态

int tot=∑|s|;
struct Node{
    int id;//s[id]结尾 
    Node *nxt[26];
}pool[tot],*rt;
void insert(string s,int id){
    Node *p=rt;
    int c;
    for(int i=0;i<s.length();i++)
    {
        c=s[i]-'0';
        if(p->nxt[c]==NULL)p->next[c]=pool+(++top);
        p=p->nxt[c];
        if(i==s.length()-1)p->id=id;
    }
}

Fail指针

AC自动机利用一个fail指针来辅助多模式串的匹配
状态u的fail指针指向另一个可识别状态v，且v是u的最长后缀，即fail[u] = 状态u的最长可识别后缀
在这里插入图片描述

求fail[u]指针

图中红色线为fail指针所指
在这里插入图片描述
所谓border，就是next[len(β)]，直观含义是除了串本身以外，使得前缀等于后缀的最长的一段前缀。
类比求next[j] = pre(s,j)的最长border
pre(s,j-1)的所有border长度为k1 = next[j-1], k2=next[next[j-1]]....
需要找到最大的k使得s[k+1] = s[j] 成立了
此时next[j] = k+1

现在我们来看fail，字典树当前的状态为p，p添加字符c的边（记为p->c）指向状态u，即p->c=u。并假设深度小于u的所以结点的fail指针都已求得
p的所有可识别后缀：k1=fail[p], k2=fail[fail[p]],.....
找到其中深度最大的状态k使得k->c 可识别（存在）
此时fail[u]= k->c

如果fail[p]->c存在：则让fail[u]=fail[p]->c.相当于在p和fail[p]后面加一个字符c，分别对应u和fail[u]
如果fail[p]->c不存在：那么继续检查fail[fail[p]]->c，一直跳fail指针直到根节点，如果真没有，那就fail[u]=rt，指向根节点

代码：

void bulid()
{
    queue<Node*>q;
    rt->fail=rt;
    for(int k=0;k<26;k++)
    {
        if(rt->nxt[k])q.push(rt->nxt[k]);
        else rt->nxt[k]=rt;
        rt->nxt[k]->fail=rt;
    }
    //bfs
    while(!q.empty())
    {
        Node *p=q.front();
        q.pop();
        for(int k=0;k<26;k++)
        {
            if(p->nxt[k])//如果有孩子 
            {
                p->nxt[k]->fail=p->fail->nxt[k];
                q.push(p->nxt[k]);
            }
            else p->nxt[k]=p->fail->nxt[k];//如果没有孩子，（相当于路径压缩） ，图中的黑线部分
        }
    }
}

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}

在这里插入图片描述
最终形态：

在这里插入图片描述

多模式匹配

建trie O(∑|S|)
求所有状态的fail指针
fail已经没有空指针，所以在图上大胆走

黄色为模式串
问模式串在t中出现几次？
直接计算模式串上有几个i不可，虽然01,010,11都是正确的（01上i出现了四次，i=2,4，5,8），但是1却不对，1上一个i也没有，但是1在t中五次
暴力向上跳fail，一直跳到rt，该路径上的串均为出现
到01时，跳fail到1，又到rt，01和1均出现一次
也就是，fail链上所有模式串都加一
代码：

int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

但是！！复杂度太高了
会被卡，
正确做法是建fail树
每个点u认fail[u]为爸爸（有点像并查集的形式）
（黄色为模式串）
在这里插入图片描述
向上fail的路径上都加一

我们能发现下列特征：
1.u->rt : 链+1
2.单点求值
3.离线操作
可以用树上差分，复杂度 O（节点个数∑|S|）
全部加完的fail树
在这里插入图片描述
模式串1的出现次数 = 子树内所有1求和 = 5
AC自动机：总复杂度：O(∑|S|+26*∑|S|+|t|)

总代码：

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int N,Q;
struct Node{
    int cnt;
    Node *nxt[26];
    Node* fail;
    vector<Node*>adj;
}*rt; 
int top=0;
Node pool[MAXN];
Node* pos[MAXN];
void insert(string s,int x){
    Node *p=rt;
    int id;
    for(int i=0;i<s.length();i++)
    {
        id=s[i]-'a';
        if(p->nxt[id]==NULL)p->nxt[id]=pool+(++top);
        p=p->nxt[id];
        if(i==s.length()-1)pos[x]=p;
    }
}
void bulid()
{
    queue<Node*>q;
    rt->fail=rt;
    for(int k=0;k<26;k++)
    {
        if(rt->nxt[k])
        {
            rt->adj.push_back(rt->nxt[k]);
            q.push(rt->nxt[k]);
        }
        else rt->nxt[k]=rt;

        rt->nxt[k]->fail=rt;
    }

    while(!q.empty())
    {
        Node *p=q.front();
        q.pop();
        for(int k=0;k<26;k++)
        {
            if(p->nxt[k])//如果有孩子 
            {
                p->nxt[k]->fail=p->fail->nxt[k];
                p->fail->nxt[k]->adj.push_back(p->nxt[k]);
                q.push(p->nxt[k]);
            }
            else p->nxt[k]=p->fail->nxt[k];//如果没有孩子，（相当于路径压缩） ，图中的黑线部分
        }
    }
}
string s,t;
void dfs(Node* p)
{
    for(int k=0;k<p->adj.size();k++)
    {
        dfs(p->adj[k]);
        p->cnt+=p->adj[k]->cnt;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>N;
    rt=pool;
    for(int i=1;i<=N;i++)
    {
        cin>>s;
        insert(s,i);
    }
    bulid();
    cin>>t;
    Node *p=rt;
    for(int i=0;i<t.length();i++)
    {
        p=p->nxt[t[i]-'a'];
        ++(p->cnt);
    }
    dfs(rt);
    for(int i=1;i<=N;i++)
    {
        cout<<pos[i]->cnt<<endl;
    }
    return 0;
}