后缀自动机SAM
title: 后缀自动机SAM
categories:
- ICPC
tags:
- null
abbrlink: 6f972cc2
date: 2023-11-19 00:00:00
后缀自动机SAM
板子：
struct SAM {
static constexpr int asz = 26;
struct Node {
int len;
int fail;
int cnt = 0;
array<int, asz> next;
Node() : len{}, fail{}, next{} {}
};
vector<Node> t;
int tot = 0;
SAM() {
init();
}
void init() {
t.assign(2, Node());
t[0].next.fill(1);
t[0].len = -1;
}
int newNode() {
t.emplace_back();
return t.size() - 1;
}
int extend(int p, int c) {
if (t[p].next[c]) {
int q = t[p].next[c];
if (t[q].len == t[p].len + 1) {
return q;
}
int nq = newNode();
t[nq].len = t[p].len + 1;
t[nq].fail = t[q].fail;
t[nq].next = t[q].next;
t[q].fail = nq;
while (t[p].next[c] == q) {
t[p].next[c] = nq;
p = t[p].fail;
}
return nq;
}
int np = newNode();
t[np].len = t[p].len + 1;
while (!t[p].next[c]) {
t[p].next[c] = np;
p = t[p].fail;
}
t[np].fail = extend(p, c);
t[np].cnt += 1;
return np;
}
int extend(int p, char c, char offset = 'a') {
return extend(p, c - offset);
}
int next(int p, int x) {
return t[p].next[x];
}
int next(int p, char c, char offset = 'a') {
return next(p, c - 'a');
}
int fail(int p) {
return t[p].fail;
}
int len(int p) {
return t[p].len;
}
int size() {
return t.size();
}
int &cnt(int p) {
return t[p].cnt;
}
void work(string s) {
int p = 1;
//vector<int> pos(1, 0);
for (auto x : s) {
p = extend(p, x);
//pos.push_back(p);
}
tot = t.size() - 1;
//return pos;
}
void getcnt(int len) {
vector<int> tong(len + 1);
vector<int> id(tot + 1);
for (int i = 1; i <= tot; i++) tong[t[i].len]++;
// 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序
for (int i = 1; i <= len; i++) tong[i] += tong[i - 1];
for (int i = 1; i <= tot; i++) id[tong[t[i].len]--] = i; // 排名为j的节点是状态i
for (int i = tot; i >= 1; i--) {
auto cur = t[id[i]];
t[cur.fail].cnt += cur.cnt;
}
// 从后往前for,自底向上更新parent的right大小
}
};
给定一个只包含小写字母的字符串 $S$。字符串的价值为出现次数乘上该子串长度，不考虑只出现一次的子串。
void solve() {
string s;
cin >> s;
SAM sam;
sam.work(s);
n = s.size();
sam.getcnt(n);
ll ans = 0;
for (int i = 2; i <= sam.tot; i++) {
if (sam.t[i].cnt <= 1)
continue;
ans = max((ll)sam.t[i].cnt * sam.len(i), ans);
}
cout << ans << endl;
}
https://www.luogu.com.cn/problem/P1368求解最小循环串：
- S 复制一份拼接在后面得到T = S + S，对T 构造SAM，然后在上面走|S| 步，每步都走最小的转移边即可。
想想为什么不会提前遇到中止节点？只有后缀会有终止节点，而长度不超过n的后缀一定在原串上会有endpos，所以肯定能走下去
void solve() {
cin >> n;
SAM sam;
int p = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p = sam.extend(p, a[i]);
}
for (int i = 1; i <= n; i++) {
p = sam.extend(p, a[i]);
}
p = 1;
vector<int>res;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 30; j++) {
if (sam.next(p, j)) {
res.push_back(j);
p = sam.next(p, j);
break;
}
}
}
for(auto x:res)cout<<x<<" ";
}
例题2.给出一个字符串S，|S| ≤ 250, 000。
令G[x] 表示S 的所有长度为x 的子串中，出现次数的最大值。
求G[1], G[2], · · · , G[|S|]。
Sol:构建S 的SAM，对于每个SAM 状态s，他能表示的子串长度范围是
(L[f(s)], L[s]]，这些子串的出现次数等价于|Right(s)|。那么问题变成用
|Right(s)| 去区间更新(L[f(s)], L[s]] 的最大值。
无脑线段树？喜提TLE。(spoj是这样的)
- 怎么优化呢
因为如果长度为len的后缀出现了x次，那这个后缀的后缀也至少出现这么多次，所以G[i] 是单调不增的，我们只用|Right(s)| 去更新G[L[s]]，然后使用倒着推标记，从后向前令G[i] = max(G[i], G[i + 1]) 即可。
void solve() {
string s;
cin >> s;
SAM sam;
sam.work(s);
n = s.size();
sam.getcnt(n);
//ll ans = 0;
vector<int> ans(n + 1);
for (int i = 2; i <= sam.tot; i++) {
ans[sam.len(i)]=max(ans[sam.len(i)],sam.cnt(i));
}
for (int i = n - 1; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
}
如何求$|Right(s)|$?
大常数做法
前面说过，不存在两个前缀位于同一个状态中，而每个前缀S[1, i] 的
Right 集合必然包括了i，因此我们在构建SAM 的时候，顺便维护
count[np] = |Right[np]] = 1。然后运行一遍dfs，求子树之和即可。小常数做法
dfs 本质为树DP，树DP 本质是按照拓扑序来进行DP，Suffix-Chain 树
的拓扑序等价于按照所有状态的L[s] 从大到小排序-> 基数排序。（板子更新成这个了
重要trick：要求我们快速定位S[l, r] 在SAM上所在的状态。
3.给出一个字符串S，|S| ≤ 200, 000，给出Q ≤ 200, 000 次询问，每次需
要回答S[l, r] 在S 中共出现了多少次
Sol:本题可以用SA 的做法，转化为区间的查询，略。
- 如果使用SAM，我们提前求出每个状态的|Right[s]|，询问就是要求我
们快速定位S[l, r] 所在的状态 - 我们知道S[l, r] 一定是S 的前缀S[1, r] 的后缀，而S 的前缀共有n 个，
我们很容易找到S 的每个前缀对应的SAM 状态节点，不妨设S[1, i] 对
应于状态pos[i]。
由于S[l, r] 是S[1, r] 的后缀，他对应的状态一定位于pos[i] 的后缀链接
上，也即我们要从pos[i] 到根root 这条树链上最浅的满足,L[x] ≥ r − l + 1 的状态。 - 使用倍增即可。
代码总结：pos数组提前开1，满足查询的1base。倍增数组注意cache，以及空间全部要多开1，因为习惯于左闭右闭。
void solve() {
string s;
cin >> s;
n = s.size();
SAM sam;
auto pos = sam.work(s);
int tot = sam.tot;
//***********************************//建fail数倍增预处理
vector<vector<int>> e(tot + 1);
for (int i = 2; i <= sam.tot; i++) {
int fa = sam.fail(i);
deb(fa, i);
deb(sam.len(fa), sam.len(i));
e[sam.fail(i)].push_back(i);
}
const int jin = __lg(tot);
vector st(jin + 1, vector<int>(tot + 1));
auto dfs = [&](auto self, int u) -> void {
for (auto v : e[u]) {
self(self, v);
st[0][v] = u;
sam.cnt(u) += sam.cnt(v);
}
};
dfs(dfs, 1);
for (int j = 1; j <= jin; j++) {
for (int i = 1; i <= tot; i++) {
st[j][i] = st[j - 1][st[j - 1][i]];
}
}
//***********************************//回答询问
cin >> m;
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
int p = pos[r]; // 注意下标偏移
for (int j = jin; j >= 0; j--) {
int nx = st[j][p];
if (sam.len(nx) >= r - l + 1) {
p = nx;
}
}
cout << sam.cnt(p) << endl;
}
}
5.给出一个字符串S，|S| ≤ 200, 000，给出Q ≤ 200, 000 次询问，每次需
要回答S[l, r] 在S[L, R] 中共出现了多少次。
Sol:我们依然将出现次数转化为满足条件的Right 的个数。
本题就是询问Right(s(S[l, r])) 中，在区间[L + r − l, R] 范围内的有多少
个值。
我们不能存储每个点的Right 集合，这是$O(n^2) $的。
前面讲过，求每个点的Right 具体都有哪些值，可以转化为子树询问，
进而变成dfs 序上的区间询问。
做法1：问题就是dfs 序上对区间[dfsl[s], dfsr[s]] 询问，有多少个数字值
在[L + r − l, R] 范围内，无脑持久化权值线段树，甚至还可以处理强制
在线。做法2：如果不要求强制在线，可以先将每个询问挂在s(S[L, R]) 上，然
后使用dsu on tree 进行离线处理。upd：这里还可以给fail树建一个开点权值线段树，然后dfs的时候做线段树合并。具体来说，还是先找到模式串对应的树上结点，在这个子树的right节点里有多少值在$[a,b]$里面。只需要对权值线段树求区间和，但是每个线段都只有当前节点的信息，所以需要合并。
struct SegmentTree {
#define mid ((l + r) >> 1)
struct TREE {
int l, r;
int cnt;
} tr[N * 20]; /// 2nlogn
int tot;
void push_up(int cur) {
tr[cur].cnt = tr[tr[cur].l].cnt + tr[tr[cur].r].cnt;
}
void change(int &cur, int l, int r, int pos, int x) {
if (!cur)
cur = ++tot;
if (l == r) {
tr[cur].cnt = 1;
return;
}
if (pos <= mid)
change(tr[cur].l, l, mid, pos, x);
else
change(tr[cur].r, mid + 1, r, pos, x);
push_up(cur);
}
int merge(int a, int b, int l, int r) {
if (!a || !b)
return a | b;
if (l == r)
return tr[a].cnt ? a : b;
int cur = ++tot;
tr[cur].l = merge(tr[a].l, tr[b].l, l, mid);
tr[cur].r = merge(tr[a].r, tr[b].r, mid + 1, r);
push_up(cur);
return cur;
}
int query(int cur, int l, int r, int ql, int qr) {
if (!cur || ql < l || qr > r || ql > qr)
return 0;
if (l == ql && r == qr)
return tr[cur].cnt;
if (qr <= mid)
return query(tr[cur].l, l, mid, ql, qr);
else if (ql > mid)
return query(tr[cur].r, mid + 1, r, ql, qr);
return query(tr[cur].l, l, mid, ql, mid) + query(tr[cur].r, mid + 1, r, mid + 1, qr);
}
} seg;
//sam函数唯一变动
auto work(string s) {
int p = 1;
vector<int> pos(1, 0);
for (auto x : s) {
p = extend(p, x);
seg.change(rt[p], 1, n, t[p].len, 1);
pos.push_back(p);
}
tot = t.size() - 1;
return pos;
}
//没了
void solve() {
string s;
cin >> s;
n = s.size();
SAM sam;
auto pos = sam.work(s);
int tot = sam.tot;
//***********************************//建fail数倍增预处理
vector<vector<int>> e(tot + 1);
for (int i = 2; i <= sam.tot; i++) {
int fa = sam.fail(i);
deb(fa, i);
deb(sam.len(fa), sam.len(i));
e[sam.fail(i)].push_back(i);
}
const int jin = __lg(tot);
vector st(jin + 1, vector<int>(tot + 1));
auto dfs = [&](auto self, int u) -> void {
for (auto v : e[u]) {
self(self, v);
st[0][v] = u;
sam.cnt(u) += sam.cnt(v);
rt[u] = seg.merge(rt[u], rt[v], 1, n);
}
};
dfs(dfs, 1);
for (int j = 1; j <= jin; j++) {
for (int i = 1; i <= tot; i++) {
st[j][i] = st[j - 1][st[j - 1][i]];
}
}
//***********************************//回答询问
cin >> m;
for (int i = 1; i <= m; i++) {
int l, r, a, b;
cin >> l >> r >> a >> b;
int p = pos[r]; // 注意下标偏移
for (int j = jin; j >= 0; j--) {
int nx = st[j][p];
if (sam.len(nx) >= r - l + 1) {
p = nx;
}
}
int ans = seg.query(rt[p], 1, n, a + r - l, b);
cout << ans << endl;
}
}
6.给出两个长度均小于100, 000 的字符串A 和B，求他们最长公共子串。
Sol:如果使用SAM，思路是构造一个串的SAM，将另一个串放在上面运行
（匹配）。
- 我们要对于每个B 的前缀B[1, i]，找到一个他的最大后缀B[i − x + 1, i]，使得这个后缀是A 的SAM 可以表示的,这其实就是在sam上走边即可。然后读入下一个字符，如果能匹配就累加长度，不能匹配就跳fail树直到能匹配。若跳到根了，则当前的公共串长度为0.
void solve() {
string s, t;cin >> s >> t;
SAM sam; sam.work(s);
int ans = 0;int res = 0;
int p = 1;
for (auto x : t) {
int tmp = sam.next(p, x);
if (tmp) {
res++;p = tmp;
} else {
int q = sam.fail(p);
while (q != 1 && sam.next(q, x) == 0) q = sam.fail(q);
// 可能根本没有这个匹配根本没有模式串的字母
p = sam.next(q, x);
if (p)res = sam.len(q) + 1;
else res = 0,p = 1;
//及时还原正确的起点
}
ans = max(ans, res);
}
cout << ans << endl;
}
9.顺着第六题这个思路考虑求：给出两个串S 和T，求公共本质不同子串个数
Sol：造S 的SAM，将T 放在上面运行，对于每个状态state 求出能表示的
最大T 的子串长度len[state]，考虑怎么求？
首先每个节点的最长公共子串已经在第六问的求解过程。设当前状态匹配的公共串长度为len，考虑后缀链接树的性质，则从该节点到根的每个点上也至少能匹配min(len,L[state])，所以我们需要拓扑序取max。这依然可以使用对长度基数排序，倒序拓扑更新。
答案是$\sum_{state}^{} len[state] − L[fa(state)]。$
///sam内部更新：
int &lc(int p) {
return t[p].lc;
}
void getlc(int len) {
vector<int> tong(len + 1);
vector<int> id(tot + 1);
for (int i = 1; i <= tot; i++) tong[t[i].len]++;
// 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序
for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
for (int i = 1; i <= tot; i++) id[tong[t[i].len]--] = i; // 排名为j的节点是状态i
for (int i = tot; i >= 1; i--) {
auto cur = t[id[i]];
deb(cur.fail, id[i]);
t[cur.fail].lc = max(t[cur.fail].lc, cur.lc);
}
// 从后往前for,自底向上更新parent的right大小
}
SAM sam;
void solve() {
string s, t;
cin >> s >> t;
sam.work(s);
n = s.size();
ll ans = 0;
int tot = sam.tot;
int tmp = 0;
int p = 1;
for (auto x : t) {
if (sam.next(p, x)) {
tmp++;
p = sam.next(p, x);
} else {
while (p > 1 && sam.next(p, x) == 0) p = sam.fail(p);
if (sam.next(p, x)) {
tmp = sam.len(p) + 1;
p = sam.next(p, x);
} else
tmp = 0;
}
sam.lc(p) = max(sam.lc(p), tmp);
}
sam.getlc(n);
for (int i = 2; i <= tot; i++) {
ans += max(0, min(sam.lc(i), sam.len(i)) - sam.len(sam.fail(i)));
}
cout << ans << endl;
}
7.给出N ≤ 10 个长度均小于100, 000 的字符串，求他们的最长公共子串
长度。
Sol：使用SAM 的话，本题是一个多模式匹配，需要将6题的思路转变一下：
构造其中一个串A1 的SAM，然后将剩余的每个串$Ai $分别在上面运行。
每次运行需要求对于SAM 的每个节点，他能表示的最长的$Ai$ 的子串长
度是多少。
- 实现是将$Ai $用前面相同的放法在SAM 上运行，然后拓扑更新取Max：
如果$Ai $的某个前缀匹配到了state 状态的len 长度，那么他一定也能匹
配后缀链接上所有点的L[state∗]。 - 运行九次后最终每个状态将会得到9 个匹配长度，将他们取Min 就可以得到这个
- 状态与9 个串的最长公共子串长度。最终每个状态全局取MAX即可
关于时间复杂度的问题：你会发现每次拓扑更新都需要多次遍历所有sam的节点，考虑应该以最短的字符串建立sam，记为minlen。则考虑字符串总长度为SUM，则最多只有SUM/minlen个，则复杂度是正确的。不然会TLE。
int &lc(int p) {
return t[p].lc;
}
int &tmplc(int p) {
return t[p].tmplc;
}
void getlc(int len) {
vector<int> tong(len + 1);
vector<int> id(tot + 1);
for (int i = 1; i <= tot; i++) tong[t[i].len]++;
// 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序
for (int i = 1; i <= n; i++) tong[i] += tong[i - 1];
for (int i = 1; i <= tot; i++) id[tong[t[i].len]--] = i; // 排名为j的节点是状态i
for (int i = tot; i >= 1; i--) {
auto cur = t[id[i]];
deb(cur.fail, id[i]);
t[cur.fail].lc = max(t[cur.fail].lc, cur.lc);
}
// 从后往前for,自底向上更新parent的right大小
}
SAM sam;
int ans = 0;
void duo(string t) {
int tot = sam.tot;
int tmp = 0;
int p = 1;
for (auto x : t) {
if (sam.next(p, x)) {
tmp++;
p = sam.next(p, x);
} else {
while (p > 1 && sam.next(p, x) == 0) p = sam.fail(p);
if (sam.next(p, x)) {
tmp = sam.len(p) + 1;
p = sam.next(p, x);
} else
tmp = 0;
}
sam.lc(p) = max(sam.lc(p), tmp);
}
sam.getlc(n);
for (int i = 1; i <= tot; i++) {
sam.tmplc(i) = min(sam.tmplc(i), sam.lc(i));
sam.lc(i) = 0;
}
}
void solve() {
cin >> m;
string s;
vector<string> v(m);
int mn = inf;
int id = 0;
for (int i = 0; i < m; i++) {
cin >> v[i];
if (mn > (int)v[i].size()) {
mn = v[i].size();
id = i;
}
}
s = v[id];
n = s.size();
sam.work(s);
// deb(s);
int tot = sam.tot;
for (int i = 0; i < m; i++) {
if (id == i)
continue;
duo(v[i]);
}
for (int i = 2; i <= tot; i++) ans = max(ans, min(sam.len(i), sam.tmplc(i)));
cout << ans << endl;
}
8.本质不同子串：造S 的SAM，$ \sum_{state} L[state] − L[f(state)]$ 即为答案
void solve() {
string s;cin>>s;
SAM sam;sam.work(s);ll ans=0;
for(int i=2;i<=sam.tot;i++)ans+=sam.len(i)-sam.len(sam.fail(i));
cout<<ans<<endl;
}
4.你有一台打字机，你需要用它打出一段只由小写字母构成的文本S。
设某个时刻，你已经打出来的文本为T，你可以执行两种操作：
- 花费A[ch] 块钱，将T 后面添加一个字符ch，得到T′ = T + ch，其
中A[′a′ −′ z′] 给定。 - 花费B 块钱，将T 的一个子串S 复制一份，添加到T 的后面，得到
T′ = T + S。
问你为了得到S，最少的花费是多少。
Sol:不难看出，本题可以用DP 解决，设Cost[i] 表示得到S[1, i] 的最小代价。
考虑如何计算Cost[i]：
- 第一种操作带来的转移是：Cost[i] ← Cost[i − 1] + A[S[i]]。
- 第二种操作要求我们求最长的S[1, i] 的后缀S[i − x + 1, i]，使得他在
S[1, i − x] 中也出现过，带来的转移是：
Cost[i] ← min(Cost[i − x · · · , i − 1]) + B。
- 但其实我们会发现这个cost数组一定是单调递增的，所以我们只需要关注最长的可行后缀，然后$O(1)$转移。怎么求这个长度x？
- 对于每个前缀S[1, i]，如何求最长的后缀S[i − x + 1, i]，使得他在
S[1, i − x] 中也出现过？
用Right 的概念对问题进行转化：S[1, i−x] 中也出现过→ Right 集合包
含[1, i − x] 中的至少一个位置→ Min(Right(S[i − x + 1, i])) ≤ i − x。
因此我们需要使用拓扑更新，得到SAM 每个状态的Min(Right(s))。然
后再配合ST 表，在S[1, i] 的后缀链接上倍增。
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
x = 0; int f = 1; char ch;
while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'),ch = getchar();
x *= f;
}
const int N = 4e5 + 5;
class SAM
{
public:
int fail[N],tr[N][26],len[N],endpos[N],tot,last;
void init()
{
for(int i = 0;i <= tot;i++) for(int j = 0;j < 26;j++) tr[i][j] = 0;
for(int i = 0;i <= tot;i++) fail[i] = len[i] = endpos[i] = 0;
tot = last = 1;
}
int ins(int x,int id)
{
int u = ++tot,p = last;
len[u] = len[last] + 1; last = u; endpos[u] = id;
while(p && tr[p][x] == 0) tr[p][x] = u,p = fail[p];
if(!p) fail[u] = 1;
else
{
int q = tr[p][x];
if(len[q] == len[p] + 1) fail[u] = q;
else
{
int cq = ++tot; endpos[tot] = 1e9;
len[cq] = len[p] + 1; fail[cq] = fail[q];
memcpy(tr[cq],tr[q],sizeof(tr[q]));
fail[u] = fail[q] = cq;
while(p && tr[p][x] == q) tr[p][x] = cq,p = fail[p];
}
}
return u;
}
}sam;
int n,s1,s2,f[N][19],pos[N];
char s[N];
LL dp[N];
vector <int> g[N];
void dfs(int u,int fa)
{
f[u][0] = fa;
for(auto x : g[u])
{
dfs(x,u);
sam.endpos[u] = min(sam.endpos[u],sam.endpos[x]);
}
}
int main()
{
scanf("%s",s + 1);
n = strlen(s + 1);
read(s1); read(s2);
sam.init();
for(int i = 1;i <= n;i++) pos[i] = sam.ins(s[i] - 'a',i);
for(int i = 2;i <= sam.tot;i++) g[sam.fail[i]].push_back(i);
dfs(1,0);
for(int j = 1;j <= 18;j++) for(int i = 1;i <= sam.tot;i++) f[i][j] = f[f[i][j - 1]][j - 1];
for(int i = 1;i <= n;i++) dp[i] = 1e17;
for(int i = 1;i <= n;i++)
{
int x = pos[i];
for(int j = 18;j >= 0;j--) if(i - sam.len[f[x][j]] < sam.endpos[f[x][j]]) x = f[x][j];
int y = sam.len[sam.fail[x]] + 1;
if(x == 0) y = 0;
if(i - y < sam.endpos[x]) x = f[x][0];
int o = min(sam.len[x],i - sam.endpos[x]);
dp[i] = min(dp[i - 1] + s1,dp[i - o] + s2);
}
printf("%lld\n",dp[n]);
return (0-0); // QwQ
}
1.补充证明：dp数组一定单调递增。第一种操作下，显然增加。对于第二种操作，我们反证，假设dp[i]<dp[i-1],dp[i]的最优决策点是j，那么说明1–j内有j+1–i的子串，则说明1-j内有j+1–i-1的子串，则$dp[i-1] \le dp[j]+s2=dp[i]$.这与假设矛盾，证毕。
2.性质证明：每次的j是单调的
- 考虑dp[i]的最优决策点是j，由dp数组单调可知，j的真实含义是最长的可行后缀。考虑i+1的决策点，j指针不可能回退。假设回退到k，说明k–i+1的串在前面出现过，但j–i+1都已经是i的最优解了，这显然，矛盾。
上面代码的核心：就是判断当前endpos表示当前节点表示的所有字符串中出现的最小端点，只有它大于转移点才能正确转移，我们需要找最小转移点。
- 采用fail树上倍增，每次判断一下是不是不符合条件，不符合就继续跳。结束以后判断边界，如果这个状态的最小长度后缀都无法满足条件，就再向上跳一步。
- 特判跳到fail树假的根节点0说明无法转移。向上跳一步一定满足条件，考虑倍增的性质。还有就是endpos介于 sam.len[sam.fail[x]] + 1和 sam.len(x)之间的情况，我们只需要取长度为min(i-endpos,sam.len(i));
11.给出一个模板串T，和n 个串Si，保证输入的Si 都是T 的子串。
Alice 和Bob 进行一场游戏，两人轮流操作，每次操作必须：
- 选择某一个串Si。
- 将Si 后面添加一个字符ch，要求S′i = Si + ch 必须也是T 的子串。
不能操作者输，Alice 先行，问谁会赢得这个游戏。
Sol:不难看出，这是一个组合Nim 游戏，每个串单独来看，就是一个字符串
版本的取石子游戏。
因此要求我们去求每个独立游戏的SG 函数，每次操作是在字符串后面
新增一个字母，很容易联想到SAM。
- 因此本题对T 构造SAM，然后再trans 转移图（DAG）上进行DP
（dfs）求解每个状态的SG 函数值。
判断所有独立游戏的SG 值异或和是否为0 即可判定游戏胜负。
void solve() {
string s;
while (cin >> s) {
SAM sam;
sam.work(s);
cin >> m;
int ans = 0;
int tot = sam.tot;
vector<int> sg(tot + 1);
vector<bool> vis(tot + 1);
auto dfs = [&](auto self, int u) {
if (vis[u])
return;
vis[u] = true;
set<ll> st;
for (int i = 0; i < 26; i++) {
if (sam.next(u, i)) {
int tmp = sam.next(u, i);
self(self, tmp);
st.insert(sg[tmp]);
}
}
while (st.count(sg[u])) sg[u]++;
};
dfs(dfs, 1);
auto cal = [&](string &t) {
int p = 1;
for (auto x : t) {
p = sam.next(p, x);
}
return sg[p];
};
for (int i = 1; i <= m; i++) {
string tt;
cin >> tt;
ans ^= cal(tt);
}
if (ans == 0)
cout << "Bob" << endl;
else
cout << "Alice" << endl;
}
}
SAM(后缀自动机)专题总结 - mikufun♘ - 博客园
给定多个模式串，每次查询给定一个字符串，问这个字符串在所有模式串中出现了多少次？（注意区分对比ac自动机解决的是模式串在查询的串中出现了多少次），这里问的是查询串出现了多少次？
- 考虑不可能提前预处理查询串的border结构，ac自动机是离线结构，所以需要sam
串之间用(‘z’+1)连接，array需要多开空间。查询的时候只需要在后缀自动机上运行，如果没有出边，说明查询的
char tmp = 'z' + 1;
void solve() {
int n;
cin >> n;
vector<string> q(n + 1);
for (int i = 1; i <= n; i++) cin >> q[i];
SAM sam;
string s;
for (int i = 1; i <= n; i++) s += q[i] + tmp;
sam.work(s);
int len = s.size();
sam.getcnt(len);
auto query = [&](string t) {
int p = 1;
for (auto x : t) {
if (sam.next(p, x) == 0)
return 0;
else
p = sam.next(p, x);
}
return sam.cnt(p);
};
for (int i = 1; i <= n; i++) {
cout << query(q[i]) << endl;
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！