记号

在本文中,一般有
n 为字符串长度。
[l, r] 为字符串的一个子串(闭区间)。
[pos] 为第pos个字符。
pre(i) 表示字符串的长度为 i 的前缀。
suf(i) 表示字符串的长度为 i 的后缀。
下标从 1 开始。

KMP

前置知识:理解 KMP 模板
O(N) 求出 1…n 的 最长非原串border

border

定义

若 pre(i) == suf(i), 我们把 i 叫做这个字符串的一个 border。

性质

性质1:
若一个字符串存在一个长为 b 的 border, 那么 n - b 是这个字符串的一个循环节。
此时我们说的循环节允许最后一个循环节不完整出现,比如12312312也可以有循环节123
证明:
虽然看上去很厉害,不过证明相当简单。
设循环节长 $l = n - b$
求证即为

因为存在长为 b 的 border,那么根据 border 的定义有:

接下来做的事情,就是将 $l = n - b$ 这个式子代入上式来消去 $b,n$,就证完了!

性质2:
border 的 border 还是 border
太简单了不写了。

应用

ProbHint
1009 GT考试KMP思路的dp,矩阵加速dp
1355 Radioborder直接应用
3670 动物园求不重叠border
3620 梦中曾见求某个范围的border是否存在
4698 Sandy的卡片最长公共子串
3942 Censor需要栈

NOI2014 动物园

维护两个东西:
p2, 前 i 个字符的小于等于n/2的最长 border
num[i], 前 i 个字符的最长 border 含有多少 border
KMP 主要利用了性质2。

#include <cstdio>
#include <cstring>
#define file(x) "zoo."#x
typedef long long ll;
const int L = 1e6 + 1;
const ll M = 1e9 + 7;
char s[L];
ll nxt[L], num[L];
ll solve() {
	int n = strlen(s + 1);
	ll res = 1;
	int p = 0, p2 = 0;
	num[1] = 1;
	for (int i = 2; i <= n; i++) {
		while (p && s[p + 1] != s[i]) p = nxt[p];
		if (s[p + 1] == s[i]) p++;
		nxt[i] = p;
		num[i] = num[p] + 1;
		while (p2 && s[p2  + 1] != s[i]) p2 = nxt[p2];
		if (s[p2 + 1] == s[i]) p2++;
		while (p2*2 > i) p2 = nxt[p2];
		res = (res*(num[p2] + 1))%M;
	}
	return res;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%s", s + 1), printf("%lld\n", solve());
}

BZOJ3620 梦中曾见

判断有长度在[k,len(s)/2]的 border 的子串 s 有多少个。
我们可以求出最长的「中间有空」的 border,然后判断是否不小于 k。
这个 border 的求法和动物园中的差不多。

#include <cstdio>
#include <cstring>
const int L = 15010;
int n, nxt[L], k;
long long ans;
char buf[L << 1];
int main() {
	scanf("%s%d", buf + 1, &k);
	for (char* s = buf; s == buf || *s; s++) {
		for (int i = 2, p = 0, p2 = 0; s[i]; i++) {
			while (p && s[p + 1] != s[i]) p = nxt[p];
			if (s[p + 1] == s[i]) p++;
			nxt[i] = p;
			while (p2 && s[p2 + 1] != s[i]) p2 = nxt[p2];
			if (s[p2 + 1] == s[i]) p2++;
			while (p2*2 + 1 > i) p2 = nxt[p2];
			if (p2 >= k) ans++;
		}
	}
	printf("%lld\n", ans);
}

BZOJ4698 SDOI2008 Sandy的卡片

题目中给出的条件可以转化为,两个序列差分后,除了第一项都相同。
在这个相等意义下的最长公共子串。
所以我们先将所有子串都差分。
然后枚举第一个串的一个后缀,在所有串上跑 KMP,对这些串上的匹配长度取最小值,就是当前后缀的答案。然后对所有后缀的答案取最大值。
注意跑 KMP 的时候强制让第一个字符匹配上,这是这题的相等条件。怎么强制看代码。

#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1010, L = 110;
int n, len[N], a[N][L], ans, nxt[L];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", len + i);
		for (int j = 1; j <= len[i]; j++) scanf("%d", &a[i][j]);
		for (int j = len[i]; j; j--) a[i][j] -= a[i][j - 1];
		a[i][1] = 1;
	}
	if (n == 1) ans = len[1];
	for (int* s = a[1], cnt = 1; cnt <= len[1]; s++, cnt++) {
		int ll = len[1] - (s - a[1]);
		for (int i = 2, p = 0; i <= ll; i++) {
			while (p && s[p + 1] !=  s[i]) p = nxt[p];
			if (!p || s[p + 1] == s[i]) p++;
			nxt[i] = p;
		}
		int an = 1e9;
		for (int i = 2; i <= n; i++) {
			int* t = a[i], nn = 0;
			for (int j = 1, p = 0; j <= len[i]; j++) {
				while (p && s[p + 1] != t[j]) p = nxt[p];
				if (!p || s[p + 1] == t[j]) p++;
				nn = std::max(nn, p);
				if (p == ll) break;
			}
			an = std::min(an, nn);
		}
		if (an != 1e9) ans = std::max(ans, an);
	}
	printf("%d\n", ans);
}

AC 自动机

不少题会在上面dp,走多少步怎么怎么样的方法数,可以用矩阵乘法。这个没什么说的。

然后就是插入一个串记录匹配次数。暴力方法是每到一个节点都把fail能走到的节点cnt++。不那么暴力的方法就是最后再按倒bfs序 cnt[fail[x]] += cnt[x]。
还有一种角度,把fail指针看成父指针,我们就得到了一颗fail树。这样每次匹配就是某个节点一直到根节点的树链上的点都cnt++。
或者不向上更新,每次只让一个点cnt++。考虑它的影响:对,就是他所有祖先实际上都被匹配了一次。那我们可以不修改他们,而是询问他们的子树和来得到他们被匹配的次数。这其实算是树上的技巧。主要在NOI打字机那道题里用了。

ProbHint
1030 文本生成器dp
2938 病毒拓扑排序
2434 阿狸的打字机fail树
2754 喵星球上的点名出题人——消音——
2580 VideoGamedp

后缀数组

先做完罗穗骞论文里的题。

ProbHint
1031-JSOI2007-字符加密Cipher复制粘贴一次再遍历sa,忽略不合法的后缀即可
1692 队列变换贪心策略。sa用来比较前缀后缀字典序
3238 差异数学+sa+单调栈
2251 2010BeijingWc 外星联络出现至少两次的子串个数。sub[i] = sub[i - 1] + n - sa[i] + 1 - h[i]可得长度从h[i]+1开始
3230 相似子串sa,用上式算出子串数,二分定位子串位置,计算长度。然后再算最长公共前缀和后缀
1396 识别子串sa+线段树(试手标记永久化的好机会)

应用

3238 差异

那个len的求和自己推式子吧。化到一个sigma就可以用了(on)。
然后后面那个求和我们能看出来是对所有后缀之间的lcp长度求和。
所以在height数组上,对于每个i,我们求后缀sak与sa[i]的lcp(也就是一段数的最小值)加起来就好了。
这个东西就和后缀数组没关系了,单纯的优化一些数求和的问题。
可以用单调栈解决。单调栈中维护有前面num个后缀到现在的最小值是val。再维护单调栈中val x num。每次答案加上val x num就行了。

如果你感觉单调栈写起来很迷,那可能是因为这里没搞清楚:

sa[i-1]       sa[i]
      \ h[i] /

看完再想想单调栈究竟在维护什么,看我代码也行。
#include <cstdio>
#include <cstring>
#include <cassert>
const int N = 5e5 + 10;
typedef long long ll;
int n, m, a[N], b[N], c[N], sa[N], rk[N], h[N], top;
char s[N];
struct T{ll v, n;}sk[N];
ll ans;
inline bool cmp(int a, int b, int j) {return rk[a] == rk[b] && rk[a + j] == rk[b + j];}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	m = 256;
	int i, j, p;
	for (i = 1; i <= n; i++) sa[i] = i, rk[i] = s[i],
		ans += (n + 1ll)*(n - i) - (i + 1ll + n)*(n - i)/2 + (n + 1ll)*(i - 1) - i*(i - 1ll)/2;
	for (j = 0; j <= n; m = p, j ? j<<=1:j=1) {
		for (i = n - j + 1, p = 0; i <= n; i++) a[++p] = i;
		memset(c, 0, sizeof(int)*(m + 1));
		for (i = 1; i <= n; i++) {
			if (sa[i] - j > 0) a[++p] = sa[i] - j;
			c[rk[i]]++;
		}
		for (i = 1; i <= m; i++) c[i] += c[i - 1];
		for (i = n; i; i--) sa[c[rk[a[i]]]--] = a[i];
		for (i = 1, p = 0 ; i <= n; i++) b[sa[i]] = cmp(sa[i], sa[i - 1], j) ? p:++p;
		memcpy(rk, b, sizeof(int)*(n + 1));
	}
	for (p = 0, i = 1; i <= n; h[rk[i++]] = p)
		for (p?p--:0, j = sa[rk[i] - 1]; s[i + p] == s[j + p]; p++);
	ll sum = 0;
	for (i = 1; i <= n; i++) {
		ll cnt = 0;
		if (i > 1) cnt++;
		while (top && sk[top - 1].v >= h[i]) {
			top--;
			cnt += sk[top].n;
			sum -= sk[top].n*sk[top].v;
		}
		sum += h[i]*cnt;
		ans = ans - 2*sum;
		sk[top++] = (T){h[i], cnt};
	}
	printf("%lld\n", ans);
}

3230 相似子串

我们回顾一下论文内容,本质不同的子串数目。考虑按sa顺序,每次加进来一个后缀,新产生 n - sa[i] + 0 个子串,其中 h[i] 个与前面的重复,所以新产生的本质不同的子串数目是前者减去后者。
再想想,新产生的这些子串是哪些呢?
是起点在 sa[i],终点必须严格大于 h[i] 的这些串。因为终点不到 h[i] 的都可以成为 sa[i-1] 的一个前缀,这说明他们在前面已经存在了。

然后根据以上我们就能二分出字典序中第x个子串是哪个后缀的前缀。设是第k个后缀。长度就是x-sub[k]+h[i]。加h[i]的原因见上面一行。
然后我们就知道了串的开头和结尾位置。剩下的就是个基本应用了。

实现上有点技巧。一定注意为了求公共前缀/后缀这里不能分隔符再倒着写一边。这样就没办法用这个后缀数组找子串位置了。所以可以先找出位置再这样reverse算。
注意子串个数和输入的询问都会爆int,巨坑

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
const int N = 2e5 + 10;
int n, m, q,  a[N], b[N], c[N], sa[N], rk[N], h[23][N], start[N][2], end[N][2];
long long ans[N], sub[N];
char s[N];
inline bool cmp(int a, int b, int j) {return rk[a] == rk[b] && rk[a + j] == rk[b + j];}
inline long long query(int l, int r) {
	if (l == r) return n - l + 1;
	l = rk[l], r = rk[r];
	if (l > r) std::swap(l, r);
	l++;
	int k = r - l + 1, p = 0;
	while ((1 << p + 1) <= k) p++;
	return min(h[p][l], h[p][r - (1 << p) + 1]);
}
void build() {
	m = 256;
	int i, j, p;
	memset(rk, 0, sizeof(rk));
	for (i = 1; i <= n; i++) sa[i] = i, rk[i] = s[i];
	for (j = 0; j <= n; m = p, j?j<<=1:j=1){
		for (i = n - j + 1, p = 0; i <= n; i++) a[++p] = i;
		memset(c, 0, sizeof(int)*(m + 1));
		for (i = 1; i <= n; i++) {
			c[rk[i]]++;
			if (sa[i] - j > 0) a[++p] = sa[i] - j;
		}
		for (i = 1; i <= m; i++) c[i] += c[i - 1];
		for (i = n; i; i--) sa[c[rk[a[i]]]--] = a[i];
		for (p = 0, i = 1; i <= n; i++) b[sa[i]] = cmp(sa[i], sa[i - 1], j) ? p : ++p;
		memcpy(rk, b, sizeof(int)*(n + 1));
	}
	for (p = 0, i = 1; i <= n; h[0][rk[i++]] = p)
		for (p?p--:0, j = sa[rk[i] - 1]; s[i + p] == s[j + p]; p++);
	for (i = 1; i < 23; i++) for (j = 1; j <= n; j++) if (j + (1 << i - 1) <= n)
		h[i][j] = min(h[i - 1][j], h[i - 1][j + (1 << i - 1)]);
	for (i = 1; i <= n; i++) sub[i] = sub[i - 1] + n - sa[i] + 1 - h[0][i];
}
int main() {
//	freopen("input", "r", stdin);
	scanf("%d%d%s", &n, &q, s + 1);
	build();
	for (int i = 1; i <= q; i++) {
		long long x, y;
		scanf("%lld%lld", &x, &y);
		int px = std::lower_bound(sub + 1, sub + n + 1, x) - sub, py = std::lower_bound(sub + 1, sub + 1 + n, y) - sub;
		if (px > n || py > n) {
			ans[i] = -1;
			continue;
		}
		x = x - sub[px - 1] + h[0][px], y = y - sub[py - 1] + h[0][py];
		px = sa[px], py = sa[py];
		start[i][0] = px, start[i][1] = py, end[i][0] = px + x - 1, end[i][1] = py + y - 1;
		long long pre = min(query(px, py), min(x, y));
		ans[i] += pre*pre;
	}
	std::reverse(s + 1, s + 1 + n);
	build();
	for (int i = 1; i <= q; i++) if (ans[i] != -1) {
		long long suf = min(query(n - end[i][0] + 1, n - end[i][1] + 1), (long long)min(end[i][0] - start[i][0] + 1, end[i][1] - start[i][1] + 1));
		ans[i] += suf*suf;
	}
	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
}
//子串个数会爆int,输入询问同理

2251 外星联络

直接看代码末尾的那几行吧。
为什么从 h[i] + 1 开始枚举?
想想上一题就知道了。这保证我们每次枚举到的串都不存在于前面,也就是没有把本质相同的串多输出了。

#include <cstdio>
#include <cstring>
#include <cassert>
const int N = 6010;
int n, m, a[N], b[N], c[N], sa[N], rk[N], h[N];
char s[N];
inline bool cmp(int a, int b, int j) {return rk[a] == rk[b] && rk[a + j] == rk[b + j];}
int main() {
//	freopen("input", "r", stdin);
	scanf("%d%s", &n, s + 1);
	m = 256;
	int i, j, p;
	for (i = 1; i <= n; i++) sa[i] = i, rk[i] = s[i];
	for (j = 0; j <= n; m = p, j?j<<=1:j=1) {
		for (i = n - j + 1, p = 0; i <= n; i++) a[++p] = i;
		for (i = 1; i <= n; i++) if (sa[i] - j > 0) a[++p] = sa[i] - j;
		memset(c, 0, sizeof(int)*(m + 1));
		for (i = 1; i <= n; i++) c[rk[i]]++;
		for (i = 1; i <= m; i++) c[i] += c[i - 1];
		for (i = n; i; i--) sa[c[rk[a[i]]]--] = a[i];
		for (i = 1, p = 0; i <= n; i++) b[sa[i]] = cmp(sa[i], sa[i - 1], j) ? p : ++p;
		memcpy(rk, b, sizeof(int)*(n + 1));
	}
	for (p = 0, i = 1; i <= n; h[rk[i++]] = p)
		for(p?p--:0, j = sa[rk[i] - 1]; s[i + p] == s[j + p]; p++);
	for (i = 1; i <= n; i++)
		for (int j = h[i] + 1; sa[i] + j - 1 <= n; j++) {
			int r = i, l = i;
			//while (l >= 1 && h[l] >= j) l--;
			while (r + 1 <= n && h[r + 1] >= j) r++;
			if (r - l + 1 > 1) printf("%d\n", r - l + 1);
		}
}

1396 识别子串

题目要求识别子串不能重复出现。
我们不妨考虑不重复出现的子串覆盖到了哪些字符。
还是按sa顺序来考虑sa[i]的前缀来考虑所有子串。
sa[i]有多少前缀重复出现过了?L = max(h[i], h[i + 1])就是其他地方出过的最长前缀。
这意味着从 L + 1 开始的子串都是合法的——没有重复出现过。
这样,{sa[i],L+1}这一个串可以成为它覆盖到的字符的识别串,长度显然。这里用个线段树把区间答案min了。
然后考虑sa[i]的其他合法前缀,L+2 … n 依然对覆盖到的字符有贡献,设这个字符位置为 p, 贡献就是 p - sa[i] + 1,其中 p >= L + 2。p也可以取到L+1,这时和上一行的情况贡献一样。
然后我们可以用个vector,把sa[i]放到位置L+2里。这个计算过程估计用代码(在我代码的末尾部分)可以看得更清楚,毕竟是非常直观的算法。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
const int N = 2e5 + 10;
int n, m, a[N], b[N], c[N], sa[N], rk[N], h[N], ans[N], val[N << 2];
char s[N];
std::vector<int> vec[N];
inline bool cmp(int a, int b, int j) {return rk[a] == rk[b] && rk[a + j] == rk[b + j];}
int q1, q2, q3;
void change(int o, int l, int r) {
	if (q1 <= l && r <= q2) val[o] = std::min(val[o], q3);
	else {
		int mid = l + r >> 1;
		if (mid >= q1) change(o<<1, l, mid);
		if (mid + 1 <= q2) change(o<<1|1, mid + 1, r);
	}
}
void get(int o, int l, int r, int nv) {
	nv = std::min(nv, val[o]);
	int mid = l + r >> 1;
	if (l == r) ans[l] = nv;
	else get(o<<1, l, mid, nv), get(o<<1|1, mid+1, r, nv);
}
int main() {
// 	freopen("input", "r", stdin);
	scanf("%s", s + 1);
	int i, j, p;
	for (i = 1; s[i]; i++) n++, sa[i] = i, rk[i] = s[i];
	m = 256;
	for (j = 0; j <= n; m = p, j?j<<=1:j=1) {
		for (i = n - j + 1, p = 0; i <= n; i++) a[++p] = i;
		memset(c, 0, sizeof(int)*(m + 1));
		for (i = 1; i <= n; i++) {
			c[rk[i]]++;
			if (sa[i] > j) a[++p] = sa[i] - j;
		}
		for (i = 1; i <= m; i++) c[i] += c[i - 1];
		for (i = n; i; i--) sa[c[rk[a[i]]]--] = a[i];
		for (i = 1, p = 0; i <= n; i++) b[sa[i]] = cmp(sa[i], sa[i - 1], j) ? p : ++p;
		memcpy(rk, b, sizeof(int)*(n + 1));
	}
	for (i = 1, p = 0; i <= n; h[rk[i++]] = p)
		for (p?p--:0, j = sa[rk[i] - 1]; s[i + p] == s[j + p]; p++);
	memset(ans, 0x3f, sizeof(ans));
	memset(val, 0x3f, sizeof(val));
	for (i = 1; i <= n; i++) {
		int u = std::max(h[i], h[i + 1]);
		vec[sa[i] + u].push_back(sa[i]);
		if (sa[i] + u <= n) {
			//for (j = sa[i]; j <= n; j++) ans[j] = std::min(ans[j], std::max(j - sa[i] - u, 0) + u + 1);
			q1 = sa[i], q2 = sa[i] + u, q3 = u + 1;
			change(1, 1, n);
		}
	}
	get(1, 1, n, 1e9);
	int mx = -1e9;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < vec[i].size(); j++) mx = std::max(vec[i][j], mx);
		printf("%d\n", std::min(i - mx + 1, ans[i]));
	}
}

后缀自动机

参考资料

  1. 后缀自动机 - 陈立杰 应该是某年 WC 的讲稿
  2. 不太好打开的一篇文章(番羽 土啬 好像可以上)
  3. 萌帝翻译
  4. fhq
  5. lazycal(里面也有很多很好的参考资料)
  6. 15年集训队论文
    推荐阅读顺序123546

广义sam
dwj
15年论文(注意15年有两篇关于sam的,这是第一篇)

Problems Set

ProbHint
SUBLEX字典序第k大子串 sam(也可以sa
LCS用一个串建sam,用第二个串跑
LCS2上题的直接扩展
2882 工艺最小循环表示。sam/sa都很简单
4516 生成魔咒输出每个前缀的不同子串。sam本来就支持在线算
4199 品酒大会还是按lcp统计
3172 单词先拼出论文建sam,再把每个单词放进去,输出right集合大小即为出现次数
2555 SubString意思是强制在线维护right。每次np实际上是从np到根right+1的修改操作,可以lct(避免了ett)
3926 诸神眷恋的幻想乡广义sam
4566 找相同子串广义sam
2946 公共串嗯,还是个多串lcs问题。不过这次用广义sam写了。
2806 Cheatsam dp
3998 弦论sublex
3673 回文串没搞懂
3277 串