【数据结构】自动机全家桶(AC、回文、后缀自动机)

int tr[N][26], id;      // TRIE
int cnt[N];                //标记字符串结尾
int fail[N];             // fail指针

void insert(string s)
{      //插入模式串
  int p = 0;
  for (int i = 0; i q;
  memset(fail, 0, sizeof(fail));
  for (int i = 0; i < 26; i++)
    if (tr[0][i])
      q.push(tr[0][i]);
  //首字符入队
  //不直接将0入队是为了避免指向自己
  while (!q.empty())
  {
    int k = q.front();
    q.pop();      //当前结点
    for (int i = 0; i < 26; i++)
    {
      if (tr[k][i])
      {
        fail[tr[k][i]] = tr[fail[k]][i];      //构建当前的fail指针
        q.push(tr[k][i]);                     //入队
      }
      else
        tr[k][i] = tr[fail[k]][i];
      //匹配到空字符，则索引到父节点fail指针对应的字符，以供后续指针的构建
      //类似并差集的路径压缩，把不存在的tr[k][i]全部指向tr[fail[k]][i]
      //这句话在后面匹配主串的时候也能帮助跳转
    }
  }
}
int query(string t)
{
  int p = 0, res = 0;
  for (int i = 0; i

• 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

二、回文自动机(回文树)

1.优秀博客链接

Palindromic Tree——回文树【处理一类回文串问题的强力工具】
回文自动机专题

2.问题模板

求解一个或多个字符串中有关回文串种类和数量的各种问题

3.使用

对给定的字符串S建立自动机，然后根据遍历自动机来得到想要的各种信息

4.本质

一个特殊的Trie，但和Trie存在一定的区别，但根结点下有两个子节点，分别代表奇/偶数回文串，每一个结点都代表在父节点串的左右各添加一个字母

5.运用

1）求前缀S[0~i]中本质不同的回文串个数
2）S中每一种回文串出现的次数
3）求S中回文串总数
4）以下标i结尾的回文串个数
5）处理多个串的相同回文串数量时，可以写成S1 + '#' + S2 +...+ '#' + Sn连接成一个字符串放入自动机

6.代码模板

struct Trie
{
  static const int MAXN = 28;
  int nxt[N][MAXN], f[N], cnt[N], num[N], len[N], c[N], last, n, L;
  string nows[N];
  int newnode(int x)
  {
    for (int i = 0; i < MAXN; ++i)
      nxt[L][i] = 0;
    cnt[L] = num[L] = 0;
    len[L] = x;
    return L++;
  }
  void init()
  {
    L = 0;
    newnode(0);
    newnode(-1);
    last = 0;
    n = 0;
    c[n] = -1;
    f[0] = 1;
  }
  int getf(int x)
  {
    while (c[n - len[x] - 1] != c[n])
      x = f[x];
    return x;
  }
  void add(int x)
  {
    x -= 'a';
    c[++n] = x;//c[i]表示第i次添加的字符
    int cur = getf(last);
    if (!nxt[cur][x])
    {
      int now = newnode(len[cur] + 2);
      f[now] = nxt[getf(f[cur])][x];
      nxt[cur][x] = now;
      num[now] = num[f[now]] + 1;
    }
    ++cnt[last = nxt[cur][x]];
  }
  int gettypecount()      //回文串种类数
  {
    return L - 2;
  }
  void count()
  {
    for (int i = L - 1; i >= 2; --i)
      cnt[f[i]] += cnt[i];
  }
  void undo()
  {
    for (int i = 2; i <= L - 1; i++)
      cnt[f[i]] -= cnt[i];
  }
  void printcount()      //打印每一种回文串的数量
  {
    count();
    for (int i = 2; i < L; i++)
      cout << cnt[i] << ' ';
    cout << endl;
    undo();
  }
  void insertStr(string s)      //插入一个字符串
  {
    for (int i = 0; i < s.size(); i++)
      add(s[i]);
  }
} PT;
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

三、后缀自动机(SAM)

1.优秀博客链接

史上最通俗的后缀自动机详解 先看这篇准没错
学习笔记 后缀自动机
【学习笔记】后缀自动机SAM
【算法与数据结构】——后缀自动机

2.问题模板

解决一个字符串S（尤其是S的子串）的匹配问题

3.使用

对S建立自动机，之后可以通过遍历自动机来得到各种子串的信息

4.本质

用优化的手段建立一个Trie，其本质上是对S的所有的后缀字符串建立一个字典树，然后进行优化空间。同时保证从根结点出发无返回的遍历到自动机上的任意一点都是S中的子串。

5.运用

有点多，似乎很多题目都可以通过SAM来解决，这里也只介绍几个经典的用法，具体还是要花时间理解SAM的具体结构和逻辑含义。
1）判断一个串是不是S的子串
2）求解S中子串的种类数
3）求解两个字符串的最长公共子串

6.代码模板

int tot = 1, last = 1;
struct Node
{
  int len = 0, fa = 0;	//len表示以该点为结尾的最长串长度
  int ch[26] = { 0 };
} node[N];
char str[N];
long long num[N];      // num数组代表子串出现次数
int h[N], e[N], ne[N], idx = 1;

void extend(int c)
{
  int p = last, np = last = ++tot;
  num[tot] = 1;
  node[np].len = node[p].len + 1;
  for (; p && !node[p].ch[c]; p = node[p].fa)
    node[p].ch[c] = np;
  if (!p)
    node[np].fa = 1;
  else
  {
    int q = node[p].ch[c];
    if (node[q].len == node[p].len + 1)
      node[np].fa = q;
    else
    {
      int nq = ++tot;
      node[nq] = node[q], node[nq].len = node[p].len + 1;
      node[q].fa = node[np].fa = nq;
      for (; p && node[p].ch[c] == q; p = node[p].fa)
        node[p].ch[c] = nq;
    }
  }
}

void add(int a, int b)
{
  e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs1(int x)      //求每个集合中的子串的出现次数(每个点代表的集合中的所有子串出现的次数是相同的)
{
  for (int i = h[x]; ~i; i = ne[i])
  {
    dfs1(e[i]);
    num[x] += num[e[i]];
  }
}

long long tynum;
void dfs2(int x)      //求子串种类数
{
  for (int i = h[x]; ~i; i = ne[i])
  {
    tynum += node[i].len - (node[node[i].fa].len + 1) + 1;
    dfs2(e[i]);
  }
}

void querysub(int l, int r)      //对子串建立自动机
{
  for (int i = 0; i <= idx; i++)
    h[i] = -1, e[i] = ne[i] = 0;
  for (int i = 1; i <= tot; i++)
  {
    auto& te = node[i];
    te.len = te.fa = 0;
    mem(te.ch, 0);
  }
  idx = 1;
  tot = last = 1;
  tynum = 0;
  for (int i = l - 1; i < r; i++)
    extend(str[i] - 'a');
  for (int i = 2; i <= tot; i++)      //绿边倒转建树
    add(node[i].fa, i);
  dfs1(1);      //出现的次数
  dfs2(1);      //子串的子串种类数
}

int getcount(string s)      //某个字符串出现的次数
{
  int p = 1;
  for (int i = 0; i < s.size(); i++)
  {
    int id = s[i] - 'a';
    if (!node[p].ch[id])
      return -1;
    else
      p = node[p].ch[id];
  }
  return num[p];
}


int lcs(string str)      //求最长公共子串
{
  int ans = 0, t = 0;
  int len = str.size();
  int p = 1;
  for (int i = 0; i < len; i++)
  {
    int x = str[i] - 'a';
    if (node[p].ch[x])
    {
      p = node[p].ch[x];
      t++;
    }
    else
    {
      while (p && !node[p].ch[x])
        p = node[p].fa;
      if (p == 0)
      {
        p = 1;
        t = 0;
      }
      else
      {
        t = node[p].len + 1;
        p = node[p].ch[x];
      }
    }
    ans = max(ans, t);
  }
  return ans;
}
void solve()
{
  mem(h, -1);
  scanf("%s", str);
  int q;
  scanf("%d", &q);
  while (q--)
  {
    int le, ri;
    scanf("%d%d", &le, &ri);
    querysub(le, ri);
    printf("%lld\n", tynum);
  }
}
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

更多自动机未完待续…

作者：Avalon Demerzel