简介
所有子串全部存下来放在一个 DFT 里，这个 DFT 有一个起点，其他都是终点。
像这样。
性质：
- 任何一条从 S 节点出发走普通边到一个其他节点所经过的路径上的字符组成的字符串，都和原串中的一个子串一一对应。（不重不漏）
- 一个除了 S 之外的节点有三个属性：第一个是 \(len\)，是记录这个节点上子串的一个特征的，之后再说，第二个是普通边（\(edge\)，简称 \(ed\)），每个节点可以向外连一个普通边。一个节点向外连出一个普通边，表示节点表示的字符串后面加上一个字母。第三个是 \(father\) 边（或者叫 \(link\) 边）。每个节点有且仅有一条 \(father\) 边并且一定往回连，这些 \(father\) 边组成一棵反向树，\(father_i\) 就是正常的树中 \(i\) 的父亲。
- （重要）每一个点表示若干个原串中的子串，这些子串都是从 S 开始经过某个路径到达这个点的。记这些子串的集合为 \(\{U\}\)。那么所有 \(\{U\}\) 中子串在原串中所有出现位置是一样的。并且每一个串都是最长串的后缀，\(\{U\}\) 中每个字符串都长度不同。证明：对于串 \(i\)，考虑 \(|i| < |j|\)，如果串 \(j\) 是它的后缀，那么 \(j\) 出现的位置都会出现 \(i\)；否则都不会出现 \(i\)。
- 建出来的树叫做 \(father\) 树，满足子节点的出现位置都是父节点的真子集，并且不会有交集（如果不是相同，就一定无交集，和上面证明一个道理）。其子节点集合的并集，并上所有父节点表示的子串中是前缀的终止位置集合，等于父节点集合。如下图：
可以发现消失掉的数字都是前缀。 - \(len\) 数组记录的就是 \(\{U\}\) 中最长串长度。最短串长度不用记录，就是父节点的最长串长度 \(+1\)。
- 一个节点想要跳转到其前面去掉一个字母的后缀，就看其是否为最短串。如果是，跳到父亲节点。否则，还在自己。如果要跳到一个前缀，那么记录返回边即可。
构造方式：一个一个“插入字符”。插入过程看板子。记图就好了。
void extend(char ch) {
int p = lst;
int np; np = lst = ++cnt;
a[np].len = a[p].len + 1;
tms[cnt] ++;
for(; p && !a[p].g[ch - 'a']; p = a[p].fa) {
a[p].g[ch - 'a'] = np;
}
if(!p) a[np].fa = 1;
else {
int q = a[p].g[ch - 'a'];
if(a[q].len==a[p].len +1){
a[np].fa=q;
}
else {
int nq=++cnt;a[nq]=a[q];
a[nq].len=a[p].len+1;
a[np].fa=a[q].fa=nq;
for(; p && a[p].g[ch-'a']==q; p = a[p].fa){
a[p].g[ch-'a']=nq;
}
}
}
}
记录任意一个子串出现次数
在 \(father\) 树上 DFS，别忘了加上每一个前缀 \(1\) 的贡献。
CF235C. Cyclical Quest
给定 \(s\) 以及 \(n\) 组询问，每组询问给定 \(t\)，求 \(s\) 的哪些子序列和 \(t\) 同构。
其中 \(a,b\) 同构定义为，\(a\) 进行循环右移若干位之后和 \(b\) 相等。
建出 SAM。
考虑怎么在 SAM 中找到删去子串前缀一个字母之后的位置。考虑一个字符串 \(k\)，对应 SAM 上节点 \(i\)。如果 \(fa_i.maxlen = |k| - 1\) 存在，那么 \(k\) 删去前缀一个字母之后跳到 \(fa_i\)。否则留在 \(i\)。这是后缀自动机的性质保证的。
循环右移，考虑断环为链。记 \(|t| = m, t' = t + t\)。考虑对于 \(i \in [0, m)\)，找到该串的出现次数。但是不一定对于每一个 \(t'_{[i, i + m - 1]}\) 能找到一个节点。于是我们用一个双指针 \(i,j\)，如果不能再找或者长度到达了 \(m\)，就 \(i\) 向右移一位（去除前缀一个字母）。否则 \(j\) 向右移一位（沿着自动机上的边走）即可。
\(t'\) 里可能有些长度为 \(m\) 的子串是重复的，也就会重复计算。这种情况在 \(t\) 包含周期的时候出现。考虑处理 \(nxt\) 数组知道周期，然后 \(i \in [0, T)\) 即可。
#include<bits/stdc++.h>
using namespace std;
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
string s;
int cnt = 1, lst = 1;
int tms[2000010];
struct node {
int len, fa;
int g[26];
}a[2000010];
vector<int> t[2000100];
void extend(char ch) {
int p = lst;
int np; np = lst = ++cnt;
a[np].len = a[p].len + 1;
tms[cnt] ++;
for(; p && !a[p].g[ch - 'a']; p = a[p].fa) {
a[p].g[ch - 'a'] = np;
}
if(!p) a[np].fa = 1;
else {
int q = a[p].g[ch - 'a'];
if(a[q].len==a[p].len +1){
a[np].fa=q;
}
else {
int nq=++cnt;a[nq]=a[q];
a[nq].len=a[p].len+1;
a[np].fa=a[q].fa=nq;
for(; p && a[p].g[ch-'a']==q; p = a[p].fa){
a[p].g[ch-'a']=nq;
}
}
}
}
void dfs(int now) {
for(int i : t[now]) {
dfs(i);
tms[now] += tms[i];
}
}
int ans;
int nxt[1000100];
void deal(string q) {
f(i, 0, (int)q.size() - 1) nxt[i] = 0;
for(int i = 1, j = 0; i < (int)q.size(); i ++) {
while((q[i] != q[j]) && j) j = nxt[j - 1];
if(q[i] == q[j]) {
nxt[i] = ++j;
}
}
int k = q.size();
int len = k - nxt[k - 1]; if(k % len != 0) len = k;
q += q;
int cur = 1;
for(int i = 0, j = 0; i < len; i ++) {
while(j - i + 1 <= k) {
char ch = q[j];
if(a[cur].g[ch - 'a']) {
cur = a[cur].g[ch - 'a'];
j ++;
}
else {
break;
}
}
if(j - i + 1 == k + 1) {
ans += tms[cur];
}
int ls = a[cur].fa;
if(cur == 1 || a[ls].len != (j - i - 1)) {
continue;
}
else {
cur = a[cur].fa;
continue;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
cin >> s;
f(i, 0, (int)s.size() - 1) extend(s[i]);
f(i, 1, cnt) {
t[a[i].fa].push_back(i);
}
dfs(1);
int m; cin >> m;
f(i, 1, m) {
string q; cin >> q; ans = 0; deal(q);
}
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
也可以不处理 \(nxt\)，因为每个节点表示的长度固定的字符串唯一，因此没有重复当且仅当长度为 \(m\) 的时候走到的节点是第一次走过。
by RNS_JKS
#include <bits/stdc++.h>
using namespace std;
#define N 2002002
#define clr(x) memset(x, 0, sizeof x)
int n, m, last;
int nxt[N][26], link[N], dp[N], cnt[N], ord[N], occur[N];
char s[N], p[N];
void extend(int c) {
int x = last, y = last = ++ m;
dp[y] = dp[x] + 1;
occur[y] = 1;
while (x && !nxt[x][c]) nxt[x][c] = y, x = link[x];
if (!x) link[y] = 1;
else {
int z = nxt[x][c];
if (dp[z] == dp[x] + 1) link[y] = z;
else {
int u = ++ m;
memcpy(nxt[u], nxt[z], sizeof nxt[u]);
link[u] = link[z], link[z] = link[y] = u;
dp[u] = dp[x] + 1;
while (x && nxt[x][c] == z) nxt[x][c] = u, x = link[x];
}
}
}
void build(char *s) {
// clr(nxt), clr(link), clr(dp), clr(occur);
n = strlen(s), m = 0;
last = ++ m;
for (int i = 0; i < n; i ++) extend(s[i] - 'a');
// clr(cnt);
for (int i = 1; i <= m; i ++) cnt[dp[i]] ++;
for (int i = 1; i <= n; i ++) cnt[i] += cnt[i-1];
for (int i = m; i >= 1; i --) ord[cnt[dp[i]]--] = i;
for (int i = m; i >= 1; i --) occur[link[ord[i]]] += occur[ord[i]];
}
int q, T, vis[N];
int main() {
// freopen("c.in", "r", stdin);
scanf("%s", s);
build(s);
scanf("%d", &q);
while (q --) {
scanf("%s", p);
T ++;
int len = strlen(p);
int x = 1, cl = 0, ans = 0;
for (int i = 0; i < len * 2 - 1; i ++) {
int c = p[i%len] - 'a';
while (x && !nxt[x][c]) x = link[x];
if (!x) x = 1;
else {
cl = min(cl, dp[x]) + 1;
x = nxt[x][c];
if (cl >= len) {
while (x && dp[link[x]] >= len) x = link[x];
if (vis[x] != T) ans += occur[x], vis[x] = T;
}
}
}
printf("%d\n", ans);
}
return 0;
}
哈希做法，考虑随机给 \(a \sim z\) 赋一个权值，然后加起来做 sum-hash。可能能过？我不好说。
标签：nxt,SAM,fa,后缀,++,len,int,自动机,节点 From： https://www.cnblogs.com/Zeardoe/p/17031966.html