[A-B-Suffix Array] 证明+基于sais的实现

前言

很棒的一道题目。（知识增加.jpg）

下面简述一下证明，因为本人水平较菜，且本篇为阅读了"Parameterized Suffix Arrays for Binary Strings"后的半笔记性质的记录，故本文证明过程可能包含：

不严谨的表述
一些疏漏
部分口胡

如有错误，非常抱歉，在此提前感谢大家的指正。

一些规定

任意字符串

下文中提到的“任意字符串”，都是指符合本题题意的字符串，即只包含'a‘和'b'两种字符的字符串。进一步说，下面讨论的字符串如无特殊说明，都是指代此类字符串。

一些定义

字符 $s[i]$ .

对于字符串 $s$ ，使用 $s[i]$ 表示字符串 $s$ 的第 $i$ 个字符（规定 $s[1]$ 为 $s$ 的第一个字符）。

子串 $s[i:j]$ .

对于字符串 $s$ ，使用 $s[i:j]$ 表示从第 $i$ 个字符到第 $j$ 个字符构成的字符串。

函数 $p(x)$ .

将一个字符串映射为另一个字符串的函数。

对于结果的第 $i$ 个字符（即 $p(s)[i]$ ），映射规则为：

$p(s)[i] = \{\begin{matrix} 0 & s[i] \neq s[j] \texttt{ for any } 1\le j < i \\ i - k & k = \max\{j \mid s[i] = s[j],\ 1 \le j < i \} \end{matrix}$ .

直观上可理解为每个字符替换为其到前一个相同字符的距离（如果不存在这样的字符，则替换为0）

函数 $f(x)$

$f(s)[i] = \{\begin{matrix} \infty & s[i] \neq s[j] \texttt{ for any } i < j \le n \\ k-i & k = \min\{j \mid s[i] = s[j],\ i < j \le n \} \end{matrix}$ .

直观上可理解为每个字符替换为其到后一个相同字符的距离（如果不存在这样的字符，则替换为 $\infty$ ）

全序关系 $\le$ . 【仅描述两个字符串之间的关系】

对于两个字符串 $x$ 和 $y$ ，定义 $x \le y$ 当且仅当：

① x是y的前缀。或②对于 $k = \min\{i \mid x[i] \neq y[i],\ 1 \le i \le n\}$ 有 $x[k] \le y[k]$ 成立。

全序关系<. 【仅描述两个字符串之间的关系】

对于两个字符串 $x$ 和 $y$ ，定义 $x < y$ 当且仅当：

① x是y的前缀。或②对于 $k = \min\{i \mid x[i] \neq y[i],\ 1 \le i \le n\}$ 有 $x[k] < y[k]$ 成立。

全序关系 $\ge$ . 【仅描述两个字符串之间的关系】

对于两个字符串 $x$ 和 $y$ ，定义 $x \ge y$ 当且仅当：

① x是y的前缀。或②对于 $k = \min\{i \mid x[i] \neq y[i],\ 1 \le i \le n\}$ 有 $x[k] \ge y[k]$ 成立。

全序关系 $>$ . 【仅描述两个字符串之间的关系】

对于两个字符串 $x$ 和 $y$ ，定义 $x > y$ 当且仅当：

① x是y的前缀。或②对于 $k = \min\{i \mid x[i] \neq y[i],\ 1 \le i \le n\}$ 有 $x[k] > y[k]$ 成立。

一些证明时用到的工具

性质(1) 若 $f(s)[i] \neq \infty$ ，则 $p(s)[i + f(s)[i]] = f(s)[i]$ .

性质(2) 若 $p(s)[i] \neq 0$ ，则 $f(s)[i - p(s)[i]] = p(s)[i]$ .

性质(3) $p(s)[1:i] = p(s[1:i])$ .

性质(4) $f(s)[i:|s|]=p(s[i:|s|])$ .

性质(5) $f(s[1:k]) \ge f(s)[i:k]$ . 其中 $1 \le k \le |s|$ . 直观的理解是，先对s截取子串后通过f(x)函数映射可能会将一些位置上的字符映射为 $\infty$ ，而这些字符在 $f(s)[i:k]$ 中不是 $\infty$ 。

性质(6) 若 $f(x) = f(y)$ ，对于位置集合 $\{a_1, \cdots, a_k\}$ 有 $x[a_1] = x[a_2] = \cdots = x[a_k]$ 成立，则必然有 $y[a_1] = \cdots = y[a_k]$ 成立。对于 $p(x)$ 也有相同性质。

性质(7) 对于位置 $k$ ，最多只可能存在1个位置 $i$ 满足等式 $k = i - p(s)[i]$ ，最多只可能存在一个位置 $j$ 满足等式 $k = j + f(s)[j]$ 。

正文

本题的问题是计算基于 $p(x)$ 的后缀数组。

目标是证明基于 $p(x)$ 的后缀数组与基于 $f(x)$ 的后缀数组等价。

如果我们能够证明对于“任意两个字符串 $s$ 和 $t$ ， $p(s) \le p(t)$ 等价于 $f(s) \ge f(t)$ ”，则可以直接证明基于 $f(x)$ 排序的后缀数组的逆序正好是基于 $p(x)$ 排序的后缀数组。

下面来证明这个命题。

1) 证明 $p(s) = p(t)\ \Leftrightarrow f(s) = f(t)$ .

先证 $p(s) = p(t) \Rightarrow f(s) = f(t)$ ：对于 $p(s)[i] = p(t)[i] \neq 0$ ，有 $f(s)[i - p(s)[i]] = p(s)[i]$ 【性质(2)】，同理 $f(t)[i - p(t)[i]] = p(t)[i]$ ，因为 $k = p(t)[i] = p(s)[i]$ ，则 $f(s)[i - k] = p(t)[i - k]$ ，这样存在一些字符因为其是该种类字符中位序最靠后的而没有被上述过程对应到，这些字符的位置对于 $s$ 和 $t$ 是相同的，根据 $f(x)$ 的定义，它们应当被填写为 $\infty$ ，则这些位置上 $f(s)$ 和 $f(t)$ 仍然相等，故 $p(s) = p(t) \Rightarrow f(s) = f(t)$ .

类似地，使用【性质(1)】可证明 $f(s) = f(t) \Rightarrow p(s) = p(t)$ 。

则 $p(s) = p(t) \Leftrightarrow f(s) = f(t)$ 得证。

2) 证明 $p(s) < p(t) \Rightarrow f(s) \ge f(t)$ .

① 若 $p(s)$ 是 $p(t)$ 的前缀，即 $p(s) = p(t)[1:|s|] = p(t[1:|s|])$ ，则 $f(s) = f(t[1:|s|])$ 【见正文1)】，由【性质(5)】知， $f(s) = f(t[1:|s|]) \ge f(t)[1:|s|] \ge f(t)$ ，则命题得证。

② 若 $p(s)$ 不是 $p(t)$ 的前缀，令 $w = \min\{i \mid p(s)[i] < p(t)[i] \}$ ， $a = p(s)[w]$ ， $b = p(t)[w]$ ，因为有 $a < b$ ，且 $a \ge 0$ ，故必要 $b > 0$ ，又根据 $p(x)$ 定义可知， $t[w - p(x)] = t[w]$ ，且字符串 $t$ 在 $w-p(x) + 1$ 到 $w - 1$ 之间一定不存在与 $t[w]$ 相同的字符，由【性质(2)】可知 $f(t)[w - p(x)] = b$ ；根据 $a<b$ 可以知道 $w - a > w - b$ ，而由 $p(x)$ 定义可知 $s[w - a] = s[w]$ ，因为 $w$ 是最小的 $p(s)$ 与 $p(t)$ 不同的位置，故只能有 $s[w - b] \neq s[w]$ 且字符串 $s$ 在 $w - p(x) + 1$ 到 $w - 1$ 之间一定都是与 $s[w]$ 相同的字符【性质(6)】，根据 $f(x)$ 的定义可知， $f(s)[w - b] > b = f(t)[w - b]$ ，于是只要证明在 $w - b$ 之前任意位置 $k$ 恒有不等式 $f(s)[k] \ge f(t)[k]$ 成立即可。一个简单的情况是，如果 $w - b = 1$ ，则已经完成证明。接下来讨论 $w - b \neq 1$ 的情形，根据假设有 $p(s)[1:w-b-1] = p(t)[1:w-b-1]$ ，即 $p(s[1:w-b-1])=p(t[1:w-b-1])$ 【性质(3)】，由【正文1)】可知， $f(s[1:w-b-1])=f(t[1:w-b-1])$ ，接下来考虑 $f(s)[1:w-b-1]$ 与 $f(t)[1:w-b-1]$ 的关系，对于满足 $f(s[1:w-b-1])[k] = f(s)[k]$ 的位置 $k$ ，显然有 $f(s)[k] = f(t)[k]$ ，且位置 $k$ 的集合与满足 $f(s)[i] \neq \infty$ 的所有位置 $i$ 所构成的集合相同，于是只需要考虑剩下的满足 $f(s)[j] = \infty$ 的位置 $j$ ，因为 $s[w-b] \neq s[w-b + 1]$ ，而字符串只有两种字符，故位置 $f(s)[j]$ 只可能是 $w -b$ 或 $w-b+1$ ，并且根据【性质(6)】，如果 $f(s)[j] = w -b$ ，则一定有 $f(t)[j] = w -b$ ，反之亦然。这样就证明了从位置 $1$ 到位置 $w - b - 1$ 恒有 $f(s)[j] = f(t)[j]$ 成立，之前已经证明了 $f(s)[w-b] > f(t)[w - b]$ ，故 $f(s) \ge f(t)$ 命题得证。

3) 证明 $f(s) > f(t) \Rightarrow p(s) \le p(t)$

① 若 $f(s)$ 是 $f(t)$ 的前缀，则 $f(s) = f(t)[1:|s|]=f(t[1:|s|])$ 【在假设条件 $f(s)$ 是 $f(t)$ 的前缀的前提下，性质(5)只能取等号，故第二个等式成立】，根据【正文1)】， $p(s) = p(t[1:|s|]) = p(t)[1:|s|] \le p(t)$ ，则命题得证。

② 若 $f(s)$ 不是 $f(t)$ 的前缀，令 $w = \min\{i \mid f(s)[i] > f(t)[i]\}$ ， $a = f(s)[i]$ ， $b = f(t)[i]$ 则根据假设有 $f(s)[1:w - 1] = f(t)[1:w - 1]$ ，通过【性质①】，即可将 $f(s)[1:w-1]$ 映射为 $p(s)[1:w-1]$ ，对于 $f(t)$ 也是同理，有 $p(s)[1:w-1] = p(t)[1:w-1]$ ，根据 $p(x)$ 的定义以及【性质(6)】可知 $p(s)[w] = p(t)[w]$ ，如果 $|s|=w$ ，则命题已得证，接下来只考虑 $|s| > w$ 的情形。由 $f(x)$ 定义可知 $f(t)[w] \ge 1$ ，先讨论 $f(t)[w] = 1$ 的情形，直观地想，根据 $f(x)$ 定义此时有 $t[w] = t[w+1]$ ，而由 $f(s)[w] > f(t)[w]$ 可知 $f(s)[w] > 1$ ，且在 $w+1$ 到 $w + a - 1$ 之间的所有字符一定与 $s[w]$ 不同，则对于所有位置 $\{i \mid 1 \le i < w\}$ ，一定有 $s[i] \neq s[w + 1]$ ，否则会违背 $f(t)[w - 1] = f(s)[w - 1]$ 的假设，则 $p(s)[w + 1] = 0 < 1 = p(t)[w + 1]$ ，此时命题得证；最后讨论 $f(t)[w] > 1$ 的情形，这个情形也比较简单，根据之前所述，在位置 $w+1$ 到 $w+a-1$ 之间所有字符一定与 $s[w]$ 不同，则对于位置 $\{k \mid w + 1 < k < w + a\}$ 总有 $s[k] = s[k - 1]$ ，即 $p(k) = 1$ ，考虑位置 $w + b$ 【 $w+a > w + b > w + 1$ 】，有 $p(t)[w + b] = f(t)[w] > 1 = p(s)[w+b]$ ，按照证明 $p(s)[k] = 1$ 的方法可以证明对于位置 $\{j\mid w + 1 < j < w + b\}$ 有 $f(t)[j] = 1$ ，即在 $w + 2$ 到 $w -b-1$ 的所有位置 $u$ 上有 $p(s)[u] = p(t)[u]$ ，另外根据【性质(1)】可知 $p(s)[w+1] = p(t)[w+1]$ ，由此可证 $p(s) < p(t)$ ，则命题得证。

综上，证明了 $p(s) = p(t)\ \Leftrightarrow f(s) = f(t)$ 的正确性，于是可以证明基于 $f(x)$ 排序的后缀数组的倒序就是本题需要的后缀数组。

实现

实现起来的话要注意一点细节，注意 $\ge$ 关系的定义，对于如果 $a$ 是 $b$ 的前缀，则要保证 $a$ > $b$ ，可以通过在字符串尾部添加一个比字符串所有中所有数都大的数来实现。
下面代码后缀排序使用sais。

#include <bits/stdc++.h>

#define lo(i, n, m) for (int i = n; i < m; i++)
#define loe(i, n, m) for (int i = n; i <= m; i++)
#define rlo(i, n, m) for (int i = n - 1; i >= m; i--)
#define rloe(i, n, m) for (int i = n; i >= m; i--)
#define pb push_back
#define mk make_pair
#define scd(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define sclf(x) scanf("%lf", &x)
#define scll(x) scanf("%lld", &x)
#define clr(a, b) memset((a), (b), sizeof(a))
#define fi first
#define se second
typedef long long ll;
using namespace std;
// const int INF = 0x3f3f3f3f;
// const int INF = 0x7fffffff;
// const LL INF = 0x3f3f3f3f3f3f3f3f;
// const LL INF = 0x7fffffffffffffff;
const int NIL = -1;
template <class T>
inline T mx(T a, T b) {return a > b ? a : b;}
template <class T>
inline T mi(T a, T b) {return a < b ? a : b;}
template <class T>
inline void sw(T &a, T &b) {
    T t = a; a = b; b = t;
}
template <class T>
inline T mabs(T x) {return x < 0 ? -x : x;}
inline char gc() {
    char ret;
    while ((ret = getchar()) == ' ' || ret == '\n' || ret == '\t');
    return ret;
}
template <class T>
inline T sq(T x) {return x * x;}

const int lim = 1e6 + 10;
char str[lim];
const int sz = lim * 128;
char _buf[sz], *bcur = _buf;
#define _ac(des, tp, sz) tp *des = (tp*)bcur; bcur += sizeof(tp)*(sz + 5)
#define LT 0
#define ST 1

int lbd[lim], rbd[lim];
inline void is(int len, int sigma, int *s, int *sa, bool *tp, int *cnt) {
    loe(i, 1, sigma) lbd[i] = cnt[i - 1], rbd[i] = cnt[i] - 1;
    lo(i, 0, len) if (sa[i] > 0 && !tp[sa[i] - 1]) sa[lbd[s[sa[i] - 1]]++] = sa[i] - 1;
    rlo(i, len, 0) if (sa[i] > 0 && tp[sa[i] - 1]) sa[rbd[s[sa[i] - 1]]--] = sa[i] - 1;
}
inline bool cmp(int *s1, int *s2, int len) {
    while (len--) if (*(s1++) != *(s2++)) return false;
    return true;
}
void sais(int len, int sigma, int *s, int *sa) {
    _ac(tp, bool, len);
    _ac(cnt, int, sigma);
    _ac(ps, int, len);
    _ac(bd, int, sigma);
    tp[len] = ST;
    s[len++] = '\0';
    rlo(i, len, 1) {
        if (s[i - 1] == s[i]) tp[i - 1] = tp[i];
        else tp[i - 1] = s[i - 1] > s[i] ? LT : ST;
        ++cnt[s[i]];
        sa[i] = -1;
    }
    ++cnt[s[0]];
    sa[0] = -1;
    loe(i, 1, sigma) {
        cnt[i] += cnt[i - 1];
        bd[i] = cnt[i] - 1;
    }
    int cc = 0;
    lo(i, 1, len) if (!tp[i - 1] && tp[i]) sa[bd[s[ps[cc++] = i]]--] = i;
    is(len, sigma, s, sa, tp, cnt);
    _ac(slen, int, len);
    _ac(sa1, int, cc);
    _ac(s1, int, cc);
    _ac(code, int, len);
    rlo(i, cc - 1, 0) slen[ps[i]] = ps[i + 1] - ps[i] + 1;
    slen[ps[cc - 1]] = 1;
    int idx = 0, cur = -1, pre = -1, ssz = 0;
    lo(i, 0, len) code[i] = -1;
    lo(i, 0, len) if ((cur = sa[i]) > 0 && !tp[sa[i] - 1] && tp[sa[i]]) {
        if (pre != -1 && slen[cur] == slen[pre] && cmp(s + pre, s + cur, slen[cur])) code[cur] = idx;
        else code[cur] = ++idx;
        pre = cur;
    }
    lo(i, 0, len) if (~code[i]) s1[ssz++] = code[i];
    if (idx == cc) lo(i, 0, cc) sa1[s1[i] - 1] = i;
    else sais(cc, idx, s1, sa1);
    bd[0] = 0;
    loe(i, 1, sigma) bd[i] = cnt[i] - 1;
    lo(i, 0, len) sa[i] = -1;
    rlo(i, cc, 0) sa[bd[s[ps[sa1[i]]]]--] = ps[sa1[i]];
    is(len, sigma, s, sa, tp, cnt);
    --len;
    lo(i, 0, len) sa[i] = sa[i + 1];
}
int sa[lim];
int lst[2];
int main() {
    int n;
    _ac(s, int, lim);
    while (~scd(n)) {
        scs(str);
        lst[0] = lst[1] = -1;
        rlo(i, n, 0) {
            s[i] = lst[str[i] - 'a'] != -1 ? lst[str[i] - 'a'] - i : n;
            lst[str[i] - 'a'] = i;
            sa[i] = 0;
        }
        s[n] = n + 1;
        sais(n + 1, n + 1, s, sa);
        rlo(i, n, 0) {
            if (i != n - 1) putchar(' ');
            printf("%d", sa[i] + 1);
        }
        putchar('\n');
    }
    return 0;
}