记号

在本文中,一般有
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$
求证即为
$$\forall i \in [1, n - l], [i] = [i + l]$$

因为存在长为 b 的 border,那么根据 border 的定义有:
$$\forall i \in [1, b], [i] = [n - b + i]$$
接下来做的事情,就是将 $l = n - b$ 这个式子代入上式来消去 $b,n$,就证完了!$$\forall i \in [1, n - l], [i] = [l + i]$$

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

应用

Prob Hint
1009 GT考试 KMP思路的dp,矩阵加速dp
1355 Radio border直接应用
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打字机那道题里用了。

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

后缀数组

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

Prob Hint
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

Prob Hint
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 Cheat sam dp
3998 弦论 sublex
3673 回文串 没搞懂
3277 串