AC自动机笔记与例题整理

首先，自动机算法是建立在字典树基础上，配合 kmp 算法进行一个多 fail 指针转移的过程。

KMP

	//ne 数组记录前 i 位的最大匹配的前后缀
    //ne[1] 显然是 0
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1])j = ne[j];
        if (p[i] == p[j + 1])j++;
        ne[i] = j;
    }
1
2
3
4
5
6
7

拓展 ↓↓↓

AC自动机建树/图

普通自动机：


void build() {
    queue<int> q;
    for (int i = 0; i < 4; i++)
        if (tr[0][i])q.push(tr[0][i]);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int p = tr[t][i];
            if (!p)continue;

            int j = ne[t];
            while (j && !tr[j][i])j = ne[j];
            j = tr[j][i];

            ne[p] = j;
            q.push(p);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

$根通常都设置为 0 ，这样有些 n e [] 就不用特别设置$
$i f (! p) co n t in u e;$
$没有把不存在的点建出来$

trie图：

void build() {
    queue<int> q;
    for (int i = 0; i < 4; i++)
        if (tr[0][i])q.push(tr[0][i]);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int p = tr[t][i];
            if (!p)tr[t][i] = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q.push(p);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

$不存在的结点直接补向了最近的 f ai l 指针$

最后就是例题时间：

$跟着神仙博客 e n 造$

搜索关键词

记录单词数，但只记一次，清空标记即可，练手题

单词

考了一个拓扑序dp，遍历到某个结点如果存在单词，这个结点 fail 路径上的单词都出现。所以逆序递推一下。

设计密码

kmp类型多状态状态机dp，把 fail 指针的位置当作状态表示的其中一维，匹配字母时更新状态，维护情况。

修复DNA

一样的状态机dp，不过是多维kmp的模式。注意维护不可行情况。

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 1e3 + 10, M = 3e5 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

unordered_map<char, int> mp = {
    {'A',0},{'G',1},{'C',2},{'T',3}
};
int tr[N][4], ne[N], tdx;
bool cnt[N];//开到总长度即可，不必*4
char s[N];
int dp[N][N];

void init() {
    for (int i = 0; i <= tdx; i++) {
        mem(tr[i], 0);
        ne[i] = cnt[i] = 0;
    }
    tdx = 0;
}

void insert(string& g) {
    int p = 0;
    for (int i = 0; i < sz(g); i++) {
        int u = mp[g[i]];
        if (!tr[p][u])tr[p][u] = ++tdx;
        p = tr[p][u];
    }
    cnt[p] = 1;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 4; i++)
        if (tr[0][i])q.push(tr[0][i]);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int& u = tr[t][i];
            if (!u)u = tr[ne[t]][i];
            else {
                ne[u] = tr[ne[t]][i];
                q.push(u);
                cnt[u] |= cnt[t];//每个致病串后接的串确实也是不合法的

                //不加此句能过是因为，dp转移是从 0 结点开始，特判了转移点是否致病
                //致病点都不能被更新，自然后接的点也不会被更新到
            }
        }
        cnt[t] |= cnt[ne[t]];

        //可能致病串"不在"此串上，即不后接，但也在此串中
       //这样就要看看此串所有的有可能的前后缀中是否有致病串
       //直接dp转移bool即可
    }
}

void solve() {
    int step = 0;
    while (cin >> n, n)
    {
        init();

        string g;
        for (int i = 1; i <= n; i++) {
            cin >> g;
            insert(g);
        }
        build();

        cin >> s + 1;
        n = strlen(s + 1);

        mem(dp, 0x3f);
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            int su = mp[s[i + 1]];
            //在循环外就用变量存起来，减少时间损耗，注意是 i + 1

            for (int j = 0; j <= tdx; j++) {
                if (dp[i][j] == INF)continue;

                for (int u = 0; u < 4; u++) {

                    int to = tr[j][u];
                    if (!cnt[to])
                        dp[i + 1][to] = min(dp[i + 1][to], dp[i][j] + (su != u));
                }
            }
        }

        int ans = INF;
        for (int j = 0; j <= tdx; j++)
            ans = min(ans, dp[n][j]);

        if (ans == INF)ans = -1;

        cout << "Case " << ++step << ": ";
        cout << ans << endl;
    }
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}
/*
*/
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

Codeforces16届黑龙江省赛E题

简单d个p，观察一下发现每个结点可以由父亲和fail指针转移得来，维护max。

洛谷：阿狸打字机（经典自动机，fail树上数据结构维护信息）

注意一些变量的含义。

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 2e5 + 10, M = 3e5 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int tr[N][26], ne[N], fa[N], tdx;
int id[N];//记录第 i 个被打印的字符串对应的结点 tdx
char s[N];

vector<int> e[N];

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) {
            q.push(tr[0][i]);
            //bug ——  e[0].push_back(tr[0][i]);
            //会导致重边，之后dfs序时没有特判每个点只进入一次
        }

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int p = tr[t][i];
            if (!p)continue;

            int j = ne[t];
            while (j && !tr[j][i])j = ne[j];
            j = tr[j][i];

            ne[p] = j;
            q.push(p);
        }
        e[ne[t]].push_back(t);
    }
}

int l[N], r[N], tim;
void dfs(int x) {
    l[x] = ++tim;
    for (int j : e[x])dfs(j);
    r[x] = tim;
}

struct BIT
{
    int tr[N];
    inline void ub(int& x) { x += x & (-x); }
    inline void db(int& x) { x -= x & (-x); }
    inline void modify(int x, int t) { for (; x <= tim; ub(x))tr[x] += t; }
    inline int query(int x) {
        int res = 0;
        for (; x > 0; db(x))res += tr[x];
        return res;
    }
}bt;

int ans[N];
struct node
{
    int x, id;
};
vector<node> qy[N];

void solve() {
    cin >> s + 1;
    n = strlen(s + 1);

    int p = 0, add = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'B') {
            p = fa[p];
        }
        else if (s[i] == 'P') {
            id[++add] = p;
        }
        else {
            int u = s[i] - 'a';
            if (!tr[p][u])tr[p][u] = ++tdx;
            fa[tr[p][u]] = p;
            p = tr[p][u];
        }
    }

    build();
    dfs(0);

    cin >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
                    //存的是字典树结点编号
        qy[b].push_back({ id[a],i });
    }

    p = 0, add = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'B') {
            bt.modify(l[p], -1);
            p = fa[p];
        }
        else if (s[i] == 'P') {
            ++add;
            for (auto v : qy[add]) {
                int x = v.x, id = v.id;
                int res = bt.query(r[x]) - bt.query(l[x] - 1);
                ans[id] = res;
            }
        }
        else {
            int u = s[i] - 'a';
            p = tr[p][u];
            bt.modify(l[p], 1);
        }
    }

    forr(i, 1, m)cout << ans[i] << endl;
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}
/*
*/
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
142
143
144
145
146
147
148
149

洛谷：Video Game G（简单自动机dp）

很模板，跟修复DNA是一类题。

洛谷：文本生成器（dp统计方案）

分可读不可读转移即可。

洛谷：Censoring G（贪心栈处理删除串问题）

删除字符串中出现的某些串，删除顺序是最早开始出现的位置。

注意题意：列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在 s 中出现的开始位置是互不相同的。

只通过字典树内当前结点是否有标记来判断存在删除串的不对的，因为有可能有某个最长后缀也可以删，这个信息存在fail路径上。

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 1e5 + 10, M = 3e5 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int tr[N][26], ne[N], cnt[N], tdx;
char str[N], s[N];
int top, id[N], stk[N];

void insert() {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!tr[p][u])tr[p][u] = ++tdx;
        p = tr[p][u];
    }
    cnt[p] = strlen(s);//每个串位置记录串大小
    //题意保证没有包含串
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) {
            q.push(tr[0][i]);
        }

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int &p = tr[t][i];
            if (!p)p = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q.push(p);
            }
        }
        cnt[t] = max(cnt[t], cnt[ne[t]]);
        //维护一个最大的可以转移的位置，最长后缀
        //题意保证没有包含串的话，出现最长就删是正确的
    }
}

void solve() {
    cin >> str + 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert();
    }
    build();

    n = strlen(str + 1);
    int p = 0;
    for (int i = 1; i <= n; i++) {
        int u = str[i] - 'a';
        int to = tr[p][u];
        stk[++top] = i;//栈里存下标才行

        if (cnt[to]) {
            //bug —— p = id[i - cnt[to]]，中间有可能已经删去，得从栈的下标中找到对应位置
            top -= cnt[to];
            p = id[stk[top]];
        }
        else p = to;

        id[i] = p;
    }

    for (int i = 1; i <= top; i++)cout << str[stk[i]];
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}
/*
*/
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

洛谷：The ABCD Murderer（自动机转数据结构优化dp）

问题可转换成：用尽可能少的给定模式串个数，可重叠覆盖 地构建出文本串。

如果当前匹配到 i 位置，i 结点 fail 路径上所有模式串都可以当作结尾，但可以发现这些模式串都是后缀匹配的关系，所以我们可以选一个长度最大的模式串。

选取之后，由于可以重叠覆盖，自然在区间 $i-L_i,i-1]$ 都可以转移过来，我们可以用数据结构维护区间最小值。

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 3e5 + 10, M = 3e5 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int tr[N][26], ne[N], cnt[N], tdx;
char str[N], s[N];

void insert() {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!tr[p][u])tr[p][u] = ++tdx;
        p = tr[p][u];
    }
    cnt[p] = (int)strlen(s);
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) {
            q.push(tr[0][i]);
        }

    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int& p = tr[t][i];
            if (!p)p = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q.push(p);
            }
        }
        cnt[t] = max(cnt[t], cnt[ne[t]]);//维护fail路径上最长模式串
    }
}

int dp[N];
struct segtree
{
    struct node {
        int l, r;
        int mi;
    }tr[N << 2];
    inline void pushup(int u) {
        tr[u].mi = min(tr[ul].mi, tr[ur].mi);
    }
    void build(int u, int l, int r) {
        tr[u] = { l,r,INF };  //assign something
        if (l == r) {
            return;
        }
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
    }
    void modify(int u, int l, int r, int v) {
        if (tr[u].l >= l && tr[u].r <= r) {
            tr[u].mi = min(tr[u].mi, v);
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)modify(ul, l, r, v);
        if (r > mid)modify(ur, l, r, v);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) {
            return tr[u].mi;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        int t = INF;
        if (l <= mid)t = query(ul, l, r);
        if (r > mid)t = min(t, query(ur, l, r));
        return t;
    }
}seg;

void solve() {
    cin >> n;
    cin >> str + 1;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert();
    }
    build();

    int p = 0;
    n = strlen(str + 1);

    seg.build(1, 0, n);
    mem(dp, 0x3f);
    dp[0] = 0;
    seg.modify(1, 0, 0, 0);

    for (int i = 1; i <= n; i++) { //标准dp
        int u = str[i] - 'a';
        p = tr[p][u];

        if (cnt[p]) {
            int l = max(0, i - cnt[p]), r = i - 1;
            dp[i] = seg.query(1, l, r) + 1;
            seg.modify(1, i, i, dp[i]);
        }
    }

    int ans = dp[n];
    //注意不能特判 ans == INF
    if (ans > INF / 2)ans = -1;
    cout << ans;
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}
/*
*/
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
142
143

CF：You Are Given Some Strings（2400的字符串匹配方案数）

首先对于任意 $s_i+s_j$ ，相当于是文本串的子串，对其切分成两部分，可以发现在计算：文本串的每个 $[1, i]$ 有多少个以 i 结尾的后缀匹配模式串，乘上，对应 $[i + 1, n]$ 倒过来以 i+1 结尾有多少个后缀模式串。

所以我们正向模式串和反向模式串分别建立正反自动机，最后在顺序遍历文本串记录f1[i]，逆序记录f2[i]。答案就是枚举累计每个 f1[i] * f2[i+1]。~~很巧妙不愧是2400的含金量~~

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 4e5 + 10, M = 3e5 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

//空间直接开两倍，别省
int tr[N][26], rtr[N][26], ne[N], cnt[N], tdx;
int f1[N], f2[N];
string str, s;

void insert(int tr[][26], string &s) {
    int p = 0;
    for (int i = 0; i < sz(s); i++) {
        int u = s[i] - 'a';
        if (!tr[p][u])tr[p][u] = ++tdx;
        p = tr[p][u];
    }
    cnt[p]++;
}

void build(int tr[][26]) {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (tr[0][i])q.push(tr[0][i]);
    }
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int &p = tr[t][i];
            if (!p)p = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q.push(p);
            }
        }
        cnt[t] += cnt[ne[t]];//统计下 i 结点结尾的所有后缀模式串
    }
}

void solve() {
    cin >> str;
    str = " " + str;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert(tr, s);
        reverse(all(s));
        insert(rtr, s);
    }

    build(tr), build(rtr);

    int p = 0;
    n = sz(str) - 1;
    for (int i = 1; i <= n; i++) {
        int u = str[i] - 'a';
        p = tr[p][u];//bug —— tr[u][p] 典
        f1[i] = cnt[p];
    }

    p = 0;
    for (int i = n; i >= 1; i--) {
        int u = str[i] - 'a';
        p = rtr[p][u];
        f2[i] = cnt[p];
    }

    ll ans = 0;
    for (int i = 1; i < n; i++)//不能重叠，是 i 和 i + 1
        ans += 1ll * f1[i] * f2[i + 1];

    cout << ans;
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}
/*
*/
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

to be continue…

相关阅读:
Golang 中的调试技巧
薪资17K，在字节外包工作是一种什么体验...
生活消费分销系统搭建开发制作
【Android】使用Retrofit2发送异步网络请求的简单案例
Oracle之SQL plus的一些经验心得
探索GmSSL+Nginx实践及原理
【OpenCV学习】第1课:加载丶修改丶显示丶保存图像
JAVA实现学生日常行为评分管理系统开源项目
Godot C# 扩展方法持续更新
STC15单片机-无线通讯（WIFI模块）

原文地址：https://blog.csdn.net/weixin_51797626/article/details/126027224