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

前言

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

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

1. 不严谨的表述
2. 一些疏漏
3. 部分口胡

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

一些规定

1. 任意字符串

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

一些定义

1. 字符.

对于字符串，使用表示字符串的第个字符（规定为的第一个字符）。

2. 子串.

对于字符串，使用表示从第个字符到第个字符构成的字符串。

3. 函数.

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

对于结果的第个字符（即），映射规则为：

.

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

4. 函数

.

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

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

对于两个字符串和，定义当且仅当：

① x是y的前缀。或②对于有成立。

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

对于两个字符串和，定义当且仅当：

① x是y的前缀。或②对于有成立。

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

对于两个字符串和，定义当且仅当：

① x是y的前缀。或②对于有成立。

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

对于两个字符串和，定义当且仅当：

① x是y的前缀。或②对于有成立。

一些证明时用到的工具

性质(1) 若，则.

性质(2) 若，则.

性质(3) .

性质(4) .

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

性质(6) 若，对于位置集合有成立，则必然有成立。对于也有相同性质。

性质(7) 对于位置，最多只可能存在1个位置满足等式，最多只可能存在一个位置满足等式。

正文

本题的问题是计算基于的后缀数组。

目标是证明基于的后缀数组与基于的后缀数组等价。

如果我们能够证明对于“任意两个字符串和，等价于”，则可以直接证明基于排序的后缀数组的逆序正好是基于排序的后缀数组。

下面来证明这个命题。

1) 证明.

先证：对于，有【性质(2)】，同理，因为，则，这样存在一些字符因为其是该种类字符中位序最靠后的而没有被上述过程对应到，这些字符的位置对于和是相同的，根据的定义，它们应当被填写为，则这些位置上和仍然相等，故.

类似地，使用【性质(1)】可证明。

则得证。

2) 证明.

① 若是的前缀，即，则【见正文1)】，由【性质(5)】知，，则命题得证。

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

3) 证明

① 若是的前缀，则【在假设条件是的前缀的前提下，性质(5)只能取等号，故第二个等式成立】，根据【正文1)】，，则命题得证。

② 若不是的前缀，令，，则根据假设有，通过【性质①】，即可将映射为，对于也是同理，有，根据 的定义以及【性质(6)】可知，如果，则命题已得证，接下来只考虑的情形。由定义可知，先讨论 的情形，直观地想，根据定义此时有，而由可知，且在到之间的所有字符一定与不同，则对于所有位置，一定有，否则会违背的假设，则，此时命题得证；最后讨论的情形，这个情形也比较简单，根据之前所述，在位置到 之间所有字符一定与不同，则对于位置总有，即，考虑位置【】，有，按照证明的方法可以证明对于位置有，即在到的所有位置上有，另外根据【性质(1)】可知，由此可证，则命题得证。

综上，证明了的正确性，于是可以证明基于排序的后缀数组的倒序就是本题需要的后缀数组。

实现

实现起来的话要注意一点细节，注意关系的定义，对于如果是的前缀，则要保证>，可以通过在字符串尾部添加一个比字符串所有中所有数都大的数来实现。
下面代码后缀排序使用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;
}