铁丝网

互相联通的梦境

0%

ac自动机学习笔记

发表于

最近很想学ac自动机。

ac自动机的用处

是用来进行多个模式串的匹配，比如给出m个单词，和一个含有n个字符的文章，问有多少个单词在文章里出现过。

Trie树

又叫字典树，是ac自动机实现的基础。结构是根结点什么都没有，之后下面的子节点每个节点保存一个字母，到一个被标记节点的路径上的所有字母组成一个单词。对于每个节点，它的每个子节点的字符都不一样。

Trie树

虽然图中节点是字符串，但实际储存的时候是单个字符。

构造步骤：

  1. 先对于所给的单词构造一个Trie树
  2. 构造fail指针，指向和当前字符串拥有最长公共后缀的字符串的结尾节点。
  3. 扫描主串匹配。

fail指针

蓝色的箭头就是fail指针。

例题：

bzoj2434

要求对多组模式串进行匹配。

做法：

1.建Trie树

根据样例建的Trie树

2.构造fail指针。

根据样例构造的fail指针

3.初步构想：由fail指针的定义，发现如果b中有字符的fail指针指向a单词的末尾，则b中包含a。如果b中有n个节点的fail指针指向a的末尾，则a在b中出现了n次。枚举y串，每次到一个节点如果fail指针指向x的末尾，计数器就加一，得到一个复杂度为O(ML)的朴素算法。（M代表询问次数，L代表字符串长度）

4.改进算法：对于一个x串，只有当y串中某个节点的fail指针指向它的末尾节点才算数。所以不妨直接把fail指针反向，建立一个fail树。因为每个节点fail指针只指向一个节点，因此它确实是个树。

构造的fail树

5.这样的话，一个末尾节点的子树中的节点就是包含它的字符串中的节点。同时我们还知道一个节点及其子树在dfs序中是连续的一段。

6.对于每一个y，把关于y的询问存在领接表里面，把y所有节点在dfs序中的位置插入树状数组，之后把关于y的每一个询问在树状数组中查询一遍。

7.“对fail树遍历一遍，得到一个DFS序，再维护一个树状数组，对原Trie树进行遍历，每访问一个节点，就修改树状数组，对树状数组中该节点的DFS序起点的位置加上1。（相当于是表示这个点存在，因为dfs头节点事实上对应的就是自己）每往回走一步，就减去1。（相当于把自己变成不存在了）如果访问到了一个y字串的末尾节点，枚举询问中每个y串对应的x串，查询树状数组中x串末尾节点从DFS序中的起始位置到结束位置的和，并记录答案。这样，我们就得到了一个时间复杂度为O(N+MlogN)的优美的算法。因为N和M都不超过105，所以这个算法是可行的。”

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define N 100000 + 5

struct Edge
{
  int nxt, v;
};

struct mp
{
  int front[N], cnt;
  Edge e[N];
  mp() {cnt = 0;}
  inline void AddEdge(int u,int v)
  {
    e[++cnt].nxt = front[u];
    e[cnt].v = v;
    front[u] = cnt;
  }
}fail, queries;
//两个前向星，一个用来记录fail树，一个记录询问。
const int root = 1;
struct node
{
  int f,son[26],fail;
}t[N];
//trie树
char s[N];
//输入字符串
int len, tot = root, strs = 0, m;
int strNode[N];
//一个字符串对应的trie节点
int queue[N];
int head[N], tail[N],cnt = 0;
//dfs需要的东西
int arr[N];
//树状数组，用来存一个节点和其子树中有多少字符串y中的节点
int ans[N];
//记录每次询问的结果
inline int query(int x)
{
  int ret = 0;
  for(; x; x-= x&(-x))
    ret += arr[x];
  return ret;
}
//树状数组的询问区间和
inline void modify(int x,int d)
{
  for(; x<= cnt; x += x & (-x))
    arr[x] += d;
}
//树状数组的修改单点值
void dfs(int x)
{
  head[x] = ++cnt; //头部时间戳
  for (int i = fail.front[x]; i; i = fail.e[i].nxt)
      dfs(fail.e[i].v);
  tail[x] = cnt; //尾部时间戳
}
//head，tail记录每次查询的树，并用cnt打标记。
int main()
{
  scanf("%s",s);
  len = strlen(s);
  int now = root;
  //开始输入询问，并对于询问建图
  scanf("%d", &m);
  for (int i = 1; i <= m; i++)
  {
    int a, b;
    scanf("%d%d",&a,&b);
    queries.AddEdge(b, a);
  }
  //建trie
  for (int i = 0; i < len; ++i)
  {
    if (s[i] == 'P') strNode[++strs] = now; //建立新的单词，标记末尾节点。
    else if (s[i] == 'B') now = t[now].f; //当前点跳回父节点
    else
    {
      if (t[now].son[s[i]-'a']) now = t[now].son[s[i]-'a']; //如果有了这个字母的子节点，就直接跳到这个子节点上。
      else
      {
        int cur = now; //否则新建一个节点，编号为++tot，父节点为当前节点
        t[now = t[now].son[s[i]-'a'] = ++tot].f =  cur;
      }
    }
  }
  //开始建立fail指针和fail树
  int l = 0, r = -1;
  for (int i = 0; i < 26; ++i)
  {
    if (t[root].son[i]) //根结点的孩子的fail指针直接指向根结点，并把它们加入队列
    {
      queue[++r] = t[root].son[i];
      fail.AddEdge(root, queue[r]);
      t[queue[r]].fail = root;
    }
  }
  for(; l <= r; ++l) //遍历队列
  {
    for (int i = 0; i < 26; ++i)
    {
      if(t[queue[l]].son[i]) //遍历每个子节点
      {
        queue[++r] = t[queue[l]].son[i]; //加入队列
        for (now = t[queue[l]].fail; now != root && !t[now].son[i]; now = t[now].fail); //不断寻找当前点的父节点fail指针指向的点，直到找到一个点的子节点的值与当前点的值相同。（fail指针保证了前面的各个位已经相同）
        t[queue[r]].fail = t[now].son[i] ? t[now].son[i] : root; //如果有的话，fail指针就指向那个节点
        fail.AddEdge(t[queue[r]].fail, queue[r]); //加边，建fail树
      }
    }
  }
    dfs(root); //求dfs序
    now = root, strs = 0;
    for (int i = 0; i < len; ++i) //开始处理询问
    {
      if (s[i] == 'B') //如果删掉了就把当前dfs头的值-1
      {
        modify(head[now], -1);
        now = t[now].f;
      }
      else if (s[i] != 'P') //否则跳到trie里面的这个点，并把dfs头+1
      {
        now = t[now].son[s[i]-'a'];
        modify(head[now], 1);
      }
      else //如果到了一个字符串的结尾 就处理与它有关的询问。strs表示当前字符串编号
      {
        for (int x = queries.front[++strs]; x; x = queries.e[x].nxt)
          ans[x] = query(tail[strNode[queries.e[x].v]]) - query(head[strNode[queries.e[x].v]] - 1);
      }
    }
  for (int i = 1; i<=m; ++i) //离线算法最后的统一输出结果
    printf("%d\n", ans[i]);
    return 0;
}
主要参考：

这里

bzoj3172

比上一道题稍微简单一些，同样是构建fail树。

上一题写了，fail树某个节点的子节点代表它被这个节点包含。

记录trie上每个节点的子节点数作为它的size，显然一个单词结尾处对应的fail树中一个节点的所有子节点都包含这个单词，而一个节点可能产生的所有单词数（它属于的所有字符串的数量）就是所有子节点的数量。因此最后的结果只要把fail树上的每个节点都加上所有的子树上的size即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1100005
using namespace std;

char s[N];
int n,a[N],h[N];
struct acam_node{
  int cnt,last,ch[N][26],sz[N],fail[N];
  void add(int x){
    scanf("%s",s+1);
    int now = 0,len = strlen(s+1);
    for (int i = 1; i <= len; i++)
    {
      int c = s[i]-'a';
      if(!ch[now][c]) ch[now][c] = ++cnt;
      now = ch[now][c]; sz[now]++;
    }
    a[x] = now;
  }
  void build(){
    int head = 0, tail = 0;
    for (int i = 0; i < 26; i++)
    {
      if(ch[0][i]) h[++tail] = ch[0][i];
    }
    while(head < tail)
    {
      int x = h[++head],y;
      for (int i = 0; i < 26; i++)
      {
        if(ch[x][i])
        {
          y = ch[x][i];
          h[++tail] = y;
          fail[y] = ch[fail[x]][i];
        }
        else
        {
          ch[x][i] = ch[fail[x]][i];
        }
      }
    }
  }
    void solve(){
      for (int i = cnt; i >= 0; i--)
      {
        sz[fail[h[i]]] += sz[h[i]];
      }
      for (int i = 1; i <= n; i++)
      {
        printf("%d\n",sz[a[i]]);
      }
    }
}acam;
int main(){
  scanf("%d",&n);
  for (int i = 1; i <= n; i++) acam.add(i);
  acam.build();
  acam.solve();
  return 0;
}