题目传送门

-------------------------------------- 过年在家无聊补一下这周做的几道AC自动机的模板题

sol:AC自动机，还是要解决跳fail边产生的重复访问，但是这次用last边已经不行了，只能拿76分。我们把跳fail边的过程放到串扫描完之后一次性进行。

• AC自动机

  #include <bits/stdc++.h>
  
  using namespace std;
  
  typedef long long LL;
  
  typedef pair<int, int> PII;
  
  const int MAXN = ;
  
  struct Trie {
  
      int son[MAXN][], fail[MAXN];
  
      int que[MAXN]; int head, tail;
  
      int cnt[MAXN]; int tot, root;
  
      int add_node() {
  
          memset(son[tot], -, sizeof(son[tot]));
  
          cnt[tot] = ;
  
          return tot ++;
  
      }
  
      void init() {
  
          head = tail = ;
  
          tot = ;
  
          root = add_node();
  
      }
  
      int insert(char* s) {
  
          int p = root;
  
          for (int i = ; s[i]; i++) {
  
              int index = s[i] - 'a';
  
              if (son[p][index] == -)
  
                  son[p][index] = add_node();
  
              p = son[p][index];
  
          }
  
          return p;
  
      }
  
      void build() {
  
          fail[root] = root;
  
          for (int i = ; i < ; i++) {
  
              if (son[root][i] == -) son[root][i] = root;
  
              else {
  
                  fail[son[root][i]] = root;
  
                  que[++ tail] = son[root][i];
  
              }
  
          }
  
          while (head != tail) {
  
              int p = que[++ head];
  
              for (int i = ; i < ; i++) {
  
                  if (son[p][i] == -) son[p][i] = son[fail[p]][i];
  
                  else {
  
                      fail[son[p][i]] = son[fail[p]][i];
  
                      que[++ tail] = son[p][i];
  
                  }
  
              }
  
          }
  
      }
  
      void slove(char* s) {
  
          int p = root;
  
          for (int i = ; s[i]; i++) {
  
              int index = s[i] - 'a';
  
              p = son[p][index];
  
              cnt[p] ++;
  
          }
  
          for (int i = tail; i >= ; i--) {
  
              int p = que[i];
  
              cnt[fail[p]] += cnt[p];
  
          }
  
      }
  
  } ac;
  
  int inde[MAXN]; // 本地运行没什么问题，洛谷叫index就报编译错误
  
  char s[];
  
  int main() {
  
      int n; ac.init();
  
      scanf("%d", &n);
  
      for (int i = ; i <= n; i++) {
  
          scanf("%s", s);
  
          inde[i] = ac.insert(s);
  
      }
  
      ac.build();
  
      scanf("%s", s); ac.slove(s);
  
      for (int i = ; i <= n; i++)
  
          printf("%d\n", ac.cnt[inde[i]]);
  
      return ;
  
  }

  经过不断地40分、60分、76分，终于搞定了。为了在最后跳fail边的时候保证深度越高的节点越先跳采用了手写队列保留bfs时候的层次关系。网上看到别人的代码据说是用拓扑的，没细看。不过感觉这里的队列就是一个对深度的拓扑排序了。