前言

• AC自动机用于进行多模式串的匹配，其衍生用途非常的多。

• AC自动机无非就是在字典树上每个节点维护一个信息fail失配指针，以在失配时快速跳到下一匹配点。

  板子

  AC自动机无非insert、build和query三种操作。

insert与普通字典树无异

void add(string s) {
  int len = s.size();
  s = ' ' + s;
  int p = 0;
  for (int i = 1; i <= len; i++) {
    if (t[p].son[s[i] - 'A'] == 0)
      t[p].son[s[i] - 'A'] = ++tot;
    p = t[p].son[s[i] - 'A'];
  }
  vis[p] = 1;//几乎都要标记末尾
}

build利用bfs转移fail指针。
具体规则为：

• 若点 有一儿子字面c，则儿子的fail指向父亲的fail的儿子c。

  并将儿子 入队。

• 否则直接将fail的儿子c当做自己的儿子。

  void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++) {
    if (t[0].son[i]) {
      q.push(t[0].son[i]);
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      int v = t[u].son[i];
      if (v) {
        t[v].fail = t[t[u].fail].son[i];
        q.push(v);
  
      } else {
        t[u].son[i] = t[t[u].fail].son[i];
      }
    }
  }
  }

  query需要进行以拓扑排序进行跳点，跳点时将fail当做边即可。

  void topu(){
    queue<int>q;
    for(int i=1;i<=tot;i++){
        if(!in[i]) q.push(i);
        
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        int v=fail[u];
        ans[v]+=ans[u];
        in[v]--;
        if(in[v]==0)q.push(v);
    }
  
  }
  void quy(string s){
    int p=0;
    int l=s.size();
    for(int i=0;i<l;i++){
        p=tr[p][s[i]-'a'];
        ans[p]++;
    }
  }