题意
给定一个字符串，求每个前缀的字典最大序子串。
注意到：
- 对于每个前缀 $s_{[1,i]} $ ，字典序最大子串的右边界一定是 \(i\) 。
- 随着着 \(i\) 的增大，字典序最大子串的左边界一定是单调不减的。
解法不分先后。
后缀数组 SA
SA 对所有后缀排了序，字符串大小问题，很自然的想到 SA 的 rk 数组的作用，答案即 $ \underset {1 \leq j \leq i} {\max}{rk_j} $ 。
但是考虑两个后缀 \(rk_i < rk_j ( i < j )\) ，但是在询问长度为 \(len\) 的前缀时 $ i $ 和 $ j $ 后缀的第一个不同字符位置大于 $ len $ ， 那么后缀 $ j $ 是后缀 $ i $ 的真前缀。也就是前缀 $ i $ 更大。只要在枚举的时候在出现不同字符的位置打标记，判断即可。因为每次改变右边界，答案对应的字符串字典序都会更大，所以更新左边界后，对于可能更大左边界 $ i $ 要判断的位置一定更右，具有单调性，所以每次判断标记对应的字符串和本身即可。
code
int mfy[MAXN];
void solve() {
for (int i = 1, p = 1; i <= n; ++i) {
if (rk[i] > rk[p]) mfy[i + LCP(i, p)] = i;
if (rk[mfy[i]] > rk[p]) {
if (mfy[i] + LCP(p, mfy[i]) <= i) p = mfy[i];
else mfy[mfy[i] + LCP(p, mfy[i])] = mfy[i];
}
printf("%d %d\n", p, i);
}
}
继续观察可能成为左边界的 $ i $， $ rk_i $ 一定比上一个可能的左边界 $ rk $ 大，而当相邻后缀比较，第一个不同的字符的位置一定非递减。故具有单调性，只需要比较相邻可能的答案是不是更大即可。
code
void solve() {
vector<int>vec = {1};
for (int i = 2; i <= n; ++i)
if (rk[i] > rk[vec.back()])vec.push_back(i);
for (int i = 1, p = 0; i <= n; ++i) {
while (p + 1 < vec.size() && vec[p + 1] + LCP(vec[p + 1], vec[p]) <= i)++p;
printf("%d %d\n", vec[p], i);
}
}
后缀自动机 SAM 离线
SAM 不仅 parent 树好用，构建的 DAWG 在比较子串大小也很有用。
考虑 SAM 对应的点 $ pos $ 代表这个点所表示的字符串集最早出现的位置，因为若多次出现，后出现的一定不可能成为答案，前出现到同一点一定更大。对于同一个点 \(pos\) 是固定的，所以能走都这个点的所有路径中，一定是最大的走法是有意义的。那么解法就呼之欲出了。目前最大子串对应原题左边界就是 \(pos - len + 1\) 即可。
code
bool vis[MAXN << 1];
void dfs(int u, int len) {
vis[u] = true;
for (int i = 25; i >= 0; i--)
if (!vis[ch[u][i]]) dfs(ch[u][i], len + 1);
if (!ans[pos[u]]) ans[pos[u]] = pos[u] - len + 1;
}
后缀树
后缀树解法和上一个解法类似。从大到小遍历所有子串，同一位置第一次没枚举到赋值即可。
后缀树因为结构原因，非常擅长解决大小问题，这里推荐一道例题2021 桂林 J. Suffix Automaton
code
void build() {
for (int i = 1; i <= siz; ++i)
e[link[i]].push_back(i);
for (int i = 0; i <= siz; ++i)
sort(all(e[i]), [&](int x, int y) { return s[pos[x] - len[i]] > s[pos[y] - len[i]]; });
}
void dfs(int u) {
for (auto v : e[u])
dfs(v);
for (int i = pos[u] - len[u] + 1; i < pos[u] - len[link[u]] + 1; ++i)
if (!ans[i])
ans[i] = pos[u];
}
这里有个问题，因为后缀树上一条边对应多字符，要全部枚举会 TLE， 考虑到一个为之只会被赋值一次，用 set 或者并查集维护即可。
code
void dfs(int u) {
for (auto v : e[u])
dfs(v);
for (auto i = st.lower_bound(pos[u] - len[u] + 1); *i < pos[u] - len[link[u]] + 1; i = st.erase(i))
ans[*i] = pos[u];
}
后缀自动机 SAM 在线
官方题解说法。考虑到一个字符串所有子串中最大的子串只需要跟着 SAM 的 DAWG 一直走最大的就找到了。那么对应 \(s\) 前 \(i\) 个字符构成字符串每次都这么找一遍就能确定左边界了。
在 DAWG 上记录目前最大走过的路径插入新字符，找最早比自己转移的位置大的点，回退到这个点然后继续更新。以为答案的左边界是不递减的，所以复杂度是 \(O(n)\) 的。
写的比较冗余，当做启发吧。
code
struct SAM { //最多2n-1个点和3n-4条边
int len[MAXN << 1], link[MAXN << 1], ch[MAXN << 1][26]; //我们记 longest(v) 为其中最长的一个字符串，记 len(v) 为它的长度。
int cnt[MAXN << 1], dep[MAXN << 1], tag[MAXN << 1], fa[MAXN << 1], pv[MAXN << 1];
int cur, lst, siz, u, reb;
SAM() { clear(); }
void clear() { //设置起始点S
memset(ch, 0, sizeof(int) * (siz + 1) * 26);
memset(cnt, 0, sizeof(int) * (siz + 1));
len[0] = 0;
link[0] = -1;
siz = 0; //siz设置成0实际上有一个点，方便标记
lst = cur = 0;
}
void extend(int c) {
reb = u;
lst = cur, cur = ++siz;
len[cur] = len[lst] + 1;
cnt[cur] = 1;
for (; ~lst && !ch[lst][c]; lst = link[lst]) {
if (tag[lst] && pv[lst] < c && dep[lst] < dep[reb])reb = lst;
ch[lst][c] = cur;
}
if (lst == -1) {
link[cur] = 0;
} else {
int q = ch[lst][c];
if (len[lst] + 1 == len[q]) {
link[cur] = q;
} else { //克隆的点是q(lst的c后继)
int clone = ++siz;
link[clone] = link[q];
len[clone] = len[lst] + 1;
link[cur] = link[q] = clone;
for (; ~lst && ch[lst][c] == q; lst = link[lst]) {
if (tag[lst] && tag[q] && ch[lst][pv[lst]] == q) {
tag[q] = 0;
tag[clone] = 1;
dep[clone] = dep[q];
fa[clone] = fa[q];
fa[ch[q][pv[q]]] = clone;
pv[clone] = pv[q];
if (reb == q)reb = clone;
if (u == q)u = clone;
}
ch[lst][c] = clone;
}
memcpy(ch[clone], ch[q], sizeof(ch[q]));
}
}
}
void update() {
while (u != reb) {
tag[u] = 0;
u = fa[u];
}
for (bool ok = true; ok;) {
ok = false;
for (int i = 25; i >= 0; --i) {
if (ch[u][i]) {
fa[ch[u][i]] = u;
dep[ch[u][i]] = dep[u] + 1;
pv[u] = i;
u = ch[u][i];
tag[u] = 1;
ok = true;
break;
}
}
}
}
}p;
void solve() {
n = inal(s + 1);
p.tag[0] = 1;
for (int i = 1; i <= n; ++i) {
p.extend(s[i] - 'a');
p.update();
printf("%d %d\n", i - p.dep[p.u] + 1, i);
}
}
border 理论
注意到，每个可能成为左边界的点，都是每次答案 \([l,i]\) 的所有 border 。我们只需要在 \(i\) 增大的时候，维护这些 border 是否可能成为新的答案即可。
我们知道 border 可以划分成 \(log\) 段，对于每一段，最短的可以判断这段是否可能成为答案。用 KMP 维护 border 之间的转移。实际上就是维护右端点逐渐靠右的一堆 border 。
code
void extend(int p, char c) {
if (!p)return fail[p + 1] = 0, void();
int t = fail[p];
while (t && s[bas + t + 1] != c) t = fail[t];
if (s[bas + t + 1] == c)++t;
fail[p + 1] = t;
}
void solve() {
n = inal(s + 1);
printf("1 1\n");
int lst = 1;
for (int i = 2; i <= n; ++i) {
int x = lst, len = lst + 1;
while (x) {
if (s[i] > s[i - lst + x]) len = x + 1; // 第一个不同的位置最靠前的更大
if (fail[x] > x / 2) {
int d = x - fail[x];
x = x % d + d;
} else x = fail[x];
}
if (s[i] > s[i - lst]) len = 1;
bas = i - len;
extend(len - 1, s[i]);
lst = len;
printf("%d %d\n", i - len + 1, i);
}
}
KMP
普通的 KMP 维护的是每个前缀的最长 border，这里的 KMP 要维护的是靠右端点的 border 的长度。但是相比 border 理论的解法，这里只比较了相邻的，和 SA 解法二同理。（但是border只需要无脑暴力跑就好了）
code
void getkmp(char* s, int n) {
int p = 0, len = 1;
for (int i = 1; i <= n; i++) {
if (s[i] > s[p]) {
p = i, len = 1;
printf("%d %d\n", p, p);
continue;
}
while (fail[len] && s[p + fail[len]] < s[i]) {
len = fail[len];
p = i - len;
}
if (s[p + fail[len]] == s[i]) {
fail[len + 1] = fail[len] + 1;
len++;
} else if (s[p + fail[len]] > s[i]) {
fail[++len] = 0;
}
printf("%d %d\n", p, i);
}
}
Lyndon word
看到题，感觉 Lyndon 分解天生适合解决这类问题。一眼，翻转字符，跑一遍 duval 不就好了。反转后 \(w_i\) 的字典序严格大于\(w_i\)的所有后缀的字典序。$w_1 \leq w_2 \leq \dots \leq w_k $。但是要特判真前缀的情况。观察发现由 Lyndon 分解本身的性质，只需要每次比较相邻的即可。
code
n = inal(s + 1);
for (int i = 1; i <= n; ++i)s[i] = 'z' - s[i] + 'a';
duval(s, n);
gap.insert(gap.begin(), 0); // 这里的gap存的是每个 Lyndon word 的右边界下标
for (int i = 1, c = 0, l = 1; i <= n; ++i) {
if (i > gap[c + 1]) {
while (i > gap[c + 1] && s[i] != s[i - gap[c + 1] + gap[c]])++c;
l = gap[c] + 1;
}
printf("%d %d\n", l, i);
}
注意到， duval 的时候，实际上向前扩展的指针对应的左端点就是枚举到的 \(i\) 。 因为每次扩展对应的子串一定是 \(ww \dots ww'\) ， \(w'\) 是 \(w\) 的真前缀。而且一定 \(i\) 开始就是最大的，否则就被划分了。没有剩下被判断到的就是本身新的最大的， \(ans[i] = i\) ，即可。 同时本解法也是我认为最简洁和优美的。
code
void duval(char* s, int n) {
for (int i = 1, j, k; i <= n;) {
if (!ans[i])ans[i] = i;
for (j = i, k = i + 1; k <= n && s[k] <= s[j]; ++k) {
if (!ans[k])ans[k] = i;
if (s[k] != s[j])j = i;
else ++j;
}
while (i <= j) {
i += k - j;
}
}
}
SS(w) 有效后缀族
这个东西在JSOI2019 节日庆典出现过。笔者也做过一些简单的解释 Lyndon 分解。即加上任意字符都是可能最小的后缀即位有效后缀。
因为 \(SS(w)\) 的大小是 \(log\) 级别的，求出 \(SS(w)\) 最长的就是。
code
void solve() { // 原：JSOI2019 节日庆典
n = inal(s + 1);
vector<int>f;
for (int i = 1; i <= n; ++i) { // Lyndon 分解 SS(w)是LOG级别的
vector<int>g;
g.push_back(i);
for (auto x : f) {
while (!g.empty() && s[x + i - g.back()] > s[i])
g.pop_back();
if (g.empty() || s[x + i - g.back()] == s[i]) {
while (!g.empty() && (i - x + 1) <= (i - g.back() + 1) * 2)
g.pop_back();
g.push_back(x);
}
}
f.swap(g);
printf("%d %d\n", f.back(), i);
}
}
总结
被迫加训的产物。题目还是很不错的，各种解法都有自己的特点，希望大家能从本题获得帮助。
还有没提到的常用方法：
标签：ICPC2021,int,题解,void,pos,len,后缀,fail,沈阳站 From： https://www.cnblogs.com/Qing17/p/18419276