本文章仅为菜鸡给自己参考，文章特别乱

nonononononononononononono

oi-wiki

自为风月马前卒

鏡音リン

诱导排序与 SA-IS 算法

[2004]后缀数组 by. 徐智磊

[2009]后缀数组——处理字符串的有力工具 by. 罗穗骞

Flying2018字符串算法学习笔记

Flying2018-SA-IS学习笔记

blackfrog

ctz’s blog

倍增+sort,O(nlog2⁡n)做法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const int N=1e6+10;
char s[N];
int n,lim;
int sa[N],rk[N<<1],ork[N<<1];

signed main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	R(i,1,n) sa[i]=i,rk[i]=s[i];
	for(lim=1;lim<n;lim<<=1)
	{
		sort(sa+1,sa+n+1,[&](int x,int y){return rk[x]==rk[y]?rk[x+lim]<rk[y+lim]:rk[x]<rk[y];});
		cpy(ork,rk,n<<1);
		//memcpy(ork,rk,sizeof(rk));
		int cnt=0;
		R(i,1,n)
		{
			if(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+lim]==ork[sa[i-1]+lim]) rk[sa[i]]=cnt;
			else rk[sa[i]]=++cnt;
		}
	}
	R(i,1,n) writesp(sa[i]);
}

倍增+基数排序O(nlog⁡n)求法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const int N=1e6+10;
#define cmp(x,y,w) (ornk[x]==ornk[y]&&ornk[x+w]==ornk[y+w])
void get_SA(char *s,int *sa,int *rnk,int n)
{
	static int m,cnt[N],osa[N],ornk[N<<1],px[N];m=0;
	R(i,1,n) ++cnt[(int)s[i]],ckmax(m,(int)s[i]);
	R(i,2,m) cnt[i]+=cnt[i-1];
	L(i,1,n) sa[cnt[(int)s[i]]--]=i;
	m=0;R(i,1,n) rnk[sa[i]]=s[sa[i]]==s[sa[i-1]]?m:++m;
	for(int lim=1;m<n;lim<<=1)
	{
		clr(cnt,m+5),cpy(ornk+1,rnk+1,n+1);
		R(i,n-lim+1,n) osa[++cnt[0]]=i;
		//L(i,n-lim+1,n) osa[++cnt[0]]=i; 
		R(i,1,n) if(sa[i]>lim) osa[++cnt[0]]=sa[i]-lim;
		//R(i,1,n) ++cnt[rnk[i]];
		R(i,1,n) ++cnt[px[i]=rnk[osa[i]]];
		R(i,2,m) cnt[i]+=cnt[i-1];
		//L(i,1,n) sa[cnt[rnk[osa[i]]]--]=osa[i];
		L(i,1,n) sa[cnt[px[i]]--]=osa[i];
		m=0;R(i,1,n) rnk[sa[i]]=cmp(sa[i],sa[i-1],lim)?m:++m;
		if(m==n) {R(i,1,n)sa[rnk[i]]=i;break;}
	}
}
int n,sa[N],rnk[N];
char s[N];
signed main()
{	
	scanf("%s",s+1);
	n=strlen(s+1);
	get_SA(s,sa,rnk,n);
	R(i,1,n) writesp(sa[i]);
}

下面为两个O(n)做法

诱导排序与 SA-IS 算法:

SA-IS全称Suffix Array Induce Sort，即诱导后缀排序。

为了方便，我们在末尾加上一个特殊字符#。我们认为特殊字符字典序最小。

用rki表示后缀i的排名,sai表示排名为i的后缀，有sarki=i。

定义：如果一段后缀i有rki>rki+1那么i为L型后缀，否则i为S型后缀。

不妨设tpi=[i是L型后缀]。特别的，特殊字符是S型后缀。

关于字典序的一个性质：

引理1.1 A<B当且仅当A[lcp(A,B)]<B[lcp(A,B)]。

证明 这个结论显然成立，因为prefix(A,lcp(A,B)−1)=prefix(B,lcp(A,B)−1)。

2. 1后缀类型

根据字符串的比较，其实我们可以很容易的得出一个后缀是L型还是S型。具体来说，如果si=si+1则tpi=tpi+1否则tpi=[si>si+1]

（这里懒得打了直接贴别人的了qwq

2.2 LMS子串

我们求出这个tp之后能推出什么呢？考虑一字符串，它一定是由若干个SS⋯SLL⋯LSS⋯构成的。

因此我们在后缀类型的S型中挑出特别的一类，记为$型。型是S型的一种，它的特殊之处在于它要求它在左边的后缀必须是L型的。（可以将其理解为一连串S$型中最靠左的一个。LMS(LeftMost S-type)便是这个意思）。

同时注意到，后缀#始终是$型的。对于每一个$型所对应上的字符，我们称为LMS字符。

而我们将位置相邻的两个LMS字符中间（包括这两个字符）所构成的子串称为LMS子串。特殊的，最后一个字符#单独作为一个平凡的LMS子串。

1
2
3
4

	  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
s[i]: m m i i s s i i s  s  i  i  p  p  i  i  #
tp[i]:L L S S L L S S L  L  S  S  L  L  L  L  S
    	  *       *         *                 *

在上面的实例中，下标为3,7,11,17都是LMS字符。

而[3,7],[7,11],[11,17],[17,17]都是LMS子串。注意这里区间都是闭区间，也就是相邻的LMS子串有1的相交。

T(75XBBQI82M97ASKNHM1SD.png

  1. 后面我们将会有更好的算法来对 LMS 子串排序，时间复杂度一致，但在实际运用中速度快很多。
  2. 注意之后会创建新字符串S1，其字符集∑ 是不同的。
  3. 判断两个 LMS 子串是否相等可以暴力判断，基于引理 2.6，可以证明其总复杂度为O(|S|)。
1
2
3
4
5
6

	  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
s[i]: m m i i s s i i s  s  i  i  p  p  i  i  #
tp[i]:L L S S L L S S L  L  S  S  L  L  L  L  S
    	  *       *         *                 *
新名称     2       2         1                 0
S1: 2 2 1 0

5_$)A(VK(GA(GG5R6Z4{90.png

2.3从SA1诱导至SA

从上面的引理2.8得知，只有获得了S1的后缀数组SA1，就可以得到所有$型后缀的相对顺序。如果我们可以利用型后缀的相对顺序来对其他的L型和S型后缀（注意*型后缀也属于S型后缀，因此会对它们进行重排，从而确保新加入的S$型后缀的顺序是对的。）进行排序，就可以完成后缀数组的计算。

在这里我们先假定SA1已经计算出来，只需考虑如何计算SA。在这之前，我们先观察一下后缀数组的形式。以aabaaaab为例，它的后缀数组是这样的：

1
2
3
4
5
6
7
8
9

#
aaaab#
aaab#
aab#
aabaaaab#
ab#
abaaaab#
b#
baaaab#

不难发现，首字母相同的后缀是连续排布的，这一点可以用反证法来证明。因此我们可以利用桶排序的思想，为每一个出现过的字符建一个桶，用SA数组来存储这些桶，每个桶之间按照字典序排列，这样就可以让后缀数组初步有序。我们对每个后缀都赋予一个后缀类型，那么在首字母一样的情况下，那么在首字母一样的情况下，S型或L型会连续分布吗？答案是肯定的。因为根据引理2.2，首字母相同的后缀如果后缀类型不同，则相对顺序是确定的。因此易知不会出现S型和L型交替出现的情况。更进一步，由于L型后缀更小，因此总是先排布L型后缀，再排布S型后缀。因此每一个字符的桶可以分为两部分，一个用于放置L型后缀，另一个则用于S型后缀。为了方便确定每一个桶的起始位置，S型后缀的桶放置是倒序的。但是如果首字母和后缀类型都一致，我们不能直接快速判断大小关系。在这里就要利用诱导排序。

诱导排序的过程分为以下几步：

  1. 将SA数组初始化为每个元素都为−1的数组。
  2. 确定每个桶S型桶的起始位置。将SA1中的每一个∗型后缀按照SA1中的顺序放入相应的桶内。
  3. 确定每个桶L型桶的起始位置。在SA数组中从左往右扫一遍。如果SAi>0且tp[SAi−1]=L，则将SAi−1代表的后缀防区对应的桶中。
  4. 重新确定每个桶S型桶的起始位置，因为所有的∗型后缀要重新被排序。由于S型桶是逆序排放的，所以这次从右至左地扫描一遍SA。如果SAi>0且tp[SAi−1]=S，则将SAi−1所代表的后缀放入对应的桶中。

这样我们就可以完成从SA1诱导到SA的排序工作。这里简单说明一下为什么这样做是正确的：首先对于所有的$型后缀，都是有序排放的。从左至右扫描SA数组实际上就是按照字典序扫描现有的已排序的后缀。对于两个相邻的L型后缀A和B，这里假设|A|>|B|，则必定有A>B。由于B会被先加入SA中，所以我们保证了A和B之间的有序性。又因为L型桶是从左往右的顺序加入的，所以所有的L型后缀会逐步地按顺序加入到SA中。最后所有的L型前缀将会有序。对于S型后缀，除了要注意是相反的顺序和重新对后缀排序外，其余的原理与L$型排序类似。

之前的讨论都是基于我们已知SA1的情况下进行的，现在我们来考虑如何计算SA1。由于S1也是一个字符串，计算其后缀数组时可以考虑两种情况。

  1. 如果S1中的每一个字符都不一样，则可以直接利用桶排序直接计算SA1。
  2. 否则，递归计算SA1。

2.4对LMS子串排序

到这里，SA-IS算法几乎已经结束了，只是还有一个问题需要解决，就是对LMS子串的排序。

之前我们所提及的，我们可以利用基数排序。虽然可以在O(|S|)的时间内完成，但是事实上，这个基数排序不但常数大而且十分复杂。

仍然使用诱导排序来完成这一任务

与之前从SA1诱导到SA的算法一样，只是我们这里将第二步改为：

确定每个桶 S型桶的起始位置。将每一个 LMS 后缀的首字母（即 LMS 字符）按照任意顺序放入对应的桶中。

待算法完成，我们会获得一个SA数组其中LMS子串之间时排好了序的。

为什么这个算法是正确的，我们需要扯到一个新的概念：LMS前缀（这个概念看上去应该是个后缀…但是原论文就是把它叫做前缀，这里也就尊重原论文的说法）

规定LMS前缀函数pre(S,i)表示(1)如果suffix(S,i)是∗型的，则pre(S,i)=Si即LMS字符的LMS前缀就是自己，所以上面说到的步骤就是将所有长度为1的LMS前缀按任意顺序放入对应的桶中。(2)否则是从si开始，到右边第一个LMS字符之间（包括首尾）的子串。同样的按照suffix(S,i)的后缀类型的不同，LMS前缀pre(S,i)也同样分为S型和L型。例如，在mmiissiissiippii中,pre(S,3)=S3=i而pre(S,4)=S[4,7]=issi。

LMS前缀之间的字典序比较遵循LMS子串中的规定（即考虑后缀类型），毕竟它们是LMS子串的子串。

OVS@L2}W29L729BSXY_YM.png

运行示例

下面将用aabaaaab作为输入字符串，展示计算其后缀数组的每一步。希望能通过这个示例能够更清晰地展现 SA-IS 算法的运作流程。由于涉及到对桶的操作，这里用 @ 表示正在被处理的元素，而用 ^ 表示每个桶的起始位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

           0  1  2  3  4  5  6  7  8
S:         a  a  b  a  a  a  a  b  #
扫描后缀类型
t:         S  S  L  S  S  S  S  L  S
LMS characters:     *              *
         |# |       a         |  b  |  # 桶的名称
SA:       -1|-1 -1 -1 -1 -1 -1|-1 -1
对LMS子串进行排序
1. 放入LMS子串
SA:       08|-1 -1 -1 -1 -1 03|-1 -1
2. 从*型LMS前缀诱导到L型LMS前缀
SA:       08|-1 -1 -1 -1 -1 03|-1 -1
          @^  ^                 ^
SA:       08|-1 -1 -1 -1 -1 03|07 -1
           ^  ^             @      ^
SA:       08|-1 -1 -1 -1 -1 03|07 02  # pre(S, 6)不是L型的
           ^  ^                @   ^
SA:       08|-1 -1 -1 -1 -1 03|07 02
           ^  ^                   @^
SA:       08|-1 -1 -1 -1 -1 03|07 02
3. 从L型LMS前缀诱导到S型前缀
SA:       08|-1 -1 -1 -1 -1 03|07 02
           ^                 ^    @^
SA:       08|-1 -1 -1 -1 -1 01|07 02
           ^              ^    @   ^
SA:       08|-1 -1 -1 -1 06 01|07 02
           ^           ^    @      ^
SA:       08|-1 -1 -1 00 06 01|07 02
           ^        ^    @         ^
SA:       08|-1 -1 05 00 06 01|07 02  # 不存在pre(S, -1)
           ^     ^    @            ^
SA:       08|-1 -1 05 00 06 01|07 02
           ^     ^ @               ^
SA:       08|-1 04 05 00 06 01|07 02
           ^  ^ @                  ^
SA:       08|03 04 05 00 06 01|07 02
           ^ @^                    ^
SA:       08|03 04 05 00 06 01|07 02  # pre(S, 7)不是S型的
          @^  ^                    ^
SA:       08|03 04 05 00 06 01|07 02
扫描并重命名LMS子串
name:      1  2
S1:       2 1 0
由于每一个字符都不一样，直接计算SA1
SA1：     2 1 0
从SA1诱导到SA
         |$ |       a         |  b  |
SA:       -1|-1 -1 -1 -1 -1 -1|-1 -1
1. 按照SA1的原顺序放入(忽略S1最后的字符)
SA:       08|-1 -1 -1 -1 -1 03|-1 -1
           ^  ^                 ^
2. 从*型后缀诱导到L型后缀
SA:       08|-1 -1 -1 -1 -1 03|-1 -1
          @^  ^                 ^
SA:       08|-1 -1 -1 -1 -1 03|07 -1
           ^  ^             @      ^
SA:       08|-1 -1 -1 -1 -1 03|07 02
           ^  ^                @   ^
SA:       08|-1 -1 -1 -1 -1 03|07 02
           ^  ^                   @^
3. 从L型后缀诱导到S型后缀
SA:       08|-1 -1 -1 -1 -1 03|07 02
           ^                 ^    @^
SA:       08|-1 -1 -1 -1 -1 01|07 02
           ^              ^    @   ^
SA:       08|-1 -1 -1 -1 06 01|07 02
           ^           ^    @      ^
SA:       08|-1 -1 -1 00 06 01|07 02
           ^        ^    @         ^
SA:       08|-1 -1 05 00 06 01|07 02
           ^     ^    @            ^
SA:       08|-1 -1 05 00 06 01|07 02
           ^     ^ @               ^
SA:       08|-1 04 05 00 06 01|07 02
           ^  ^ @                  ^
SA:       08|03 04 05 00 06 01|07 02  # pre(S, 2)是L型
           ^ @^                    ^
SA:       08|03 04 05 00 06 01|07 02
          @^  ^                    ^
后缀数组构造完毕
SA: 8 3 4 5 0 6 1 7 2

return SA

具体实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

// 后缀类型
#define L_TYPE 0
#define S_TYPE 1

// 判断一个字符是否为LMS字符
inline bool is_lms_char(int *type, int x) {
    return x > 0 && type[x] == S_TYPE && type[x - 1] == L_TYPE;
}

// 判断两个LMS子串是否相同
inline bool equal_substring(int *S, int x, int y, int *type) {
    do {
        if (S[x] != S[y])
            return false;
        x++, y++;
    } while (!is_lms_char(type, x) && !is_lms_char(type, y));

    return S[x] == S[y];
}

// 诱导排序(从*型诱导到L型、从L型诱导到S型)
// 调用之前应将*型按要求放入SA中
inline void induced_sort(int *S, int *SA, int *type, int *bucket, int *lbucket,
                         int *sbucket, int n, int SIGMA) {
    for (int i = 0; i <= n; i++)
        if (SA[i] > 0 && type[SA[i] - 1] == L_TYPE)
            SA[lbucket[S[SA[i] - 1]]++] = SA[i] - 1;
    for (int i = 1; i <= SIGMA; i++)  // Reset S-type bucket
        sbucket[i] = bucket[i] - 1;
    for (int i = n; i >= 0; i--)
        if (SA[i] > 0 && type[SA[i] - 1] == S_TYPE)
            SA[sbucket[S[SA[i] - 1]]--] = SA[i] - 1;
}

// SA-IS主体
// S是输入字符串，length是字符串的长度, SIGMA是字符集的大小
static int *SAIS(int *S, int length, int SIGMA) {
    int n = length - 1;
    int *type = new int[n + 1];  // 后缀类型
    int *position = new int[n + 1];  // 记录LMS子串的起始位置
    int *name = new int[n + 1];  // 记录每个LMS子串的新名称
    int *SA = new int[n + 1];  // SA数组
    int *bucket = new int[SIGMA];  // 每个字符的桶
    int *lbucket = new int[SIGMA];  // 每个字符的L型桶的起始位置
    int *sbucket = new int[SIGMA];  // 每个字符的S型桶的起始位置

    // 初始化每个桶
    memset(bucket, 0, sizeof(int) * (SIGMA + 1));
    for (int i = 0; i <= n; i++)
        bucket[S[i]]++;
    for (int i = 1; i <= SIGMA; i++) {
        bucket[i] += bucket[i - 1];
        lbucket[i] = bucket[i - 1];
        sbucket[i] = bucket[i] - 1;
    }

    // 确定后缀类型(利用引理2.1)
    type[n] = S_TYPE;
    for (int i = n - 1; i >= 0; i--) {
        if (S[i] < S[i + 1])
            type[i] = S_TYPE;
        else if (S[i] > S[i + 1])
            type[i] = L_TYPE;
        else
            type[i] = type[i + 1];
    }

    // 寻找每个LMS子串
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (type[i] == S_TYPE && type[i - 1] == L_TYPE)
            position[cnt++] = i;

    // 对LMS子串进行排序
    fill(SA, SA + n + 1, -1);
    for (int i = 0; i < cnt; i++)
        SA[sbucket[S[position[i]]]--] = position[i];
    induced_sort(S, SA, type, bucket, lbucket, sbucket, n, SIGMA);

    // 为每个LMS子串命名
    fill(name, name + n + 1, -1);
    int lastx = -1, namecnt = 1;  // 上一次处理的LMS子串与名称的计数
    bool flag = false;  // 这里顺便记录是否有重复的字符
    for (int i = 1; i <= n; i++) {
        int x = SA[i];

        if (is_lms_char(type, x)) {
            if (lastx >= 0 && !equal_substring(S, x, lastx, type))
                namecnt++;
            // 因为只有相同的LMS子串才会有同样的名称
            if (lastx >= 0 && namecnt == name[lastx])
                flag = true;

            name[x] = namecnt;
            lastx = x;
        }
    }  // for
    name[n] = 0;

    // 生成S1
    int *S1 = new int[cnt];
    int pos = 0;
    for (int i = 0; i <= n; i++)
        if (name[i] >= 0)
            S1[pos++] = name[i];

    int *SA1;
    if (!flag) {
        // 直接计算SA1
        SA1 = new int[cnt + 1];

        for (int i = 0; i < cnt; i++)
            SA1[S1[i]] = i;
    } else
        SA1 = SAIS(S1, cnt, namecnt);  // 递归计算SA1

    // 从SA1诱导到SA
    lbucket[0] = sbucket[0] = 0;
    for (int i = 1; i <= SIGMA; i++) {
        lbucket[i] = bucket[i - 1];
        sbucket[i] = bucket[i] - 1;
    }
    fill(SA, SA + n + 1, -1);
    for (int i = cnt - 1; i >= 0; i--)  // 这里是逆序扫描SA1，因为SA中S型桶是倒序的
        SA[sbucket[S[position[SA1[i]]]]--] = position[SA1[i]];
    induced_sort(S, SA, type, bucket, lbucket, sbucket, n, SIGMA);

    // 后缀数组计算完毕
    return SA;
}

XJ的孔姥爷较通俗易懂版：

比如：

1
2
3

a a b a a b b a c b a b #
S S L S S L L S L L S L S
      *       *     *   *

那么LMS子串就是[4,8],[8,11],[11,13]

然后我们将这些子串排序得到Missing or unrecognized delimiter for \left。（大概就是rk）

可以证明的是，如果两个后缀的位置同属于lms子串的分界点，那么这两个后缀的比较相当于在排序后的LMS子串的后缀比较。

比如[8,13],[11,13]的比较就可以转换成431,31的比较。

如果子串互不相等，相当于倍增后缀排序里字符两两不同一样，直接桶排序即可。

那么如果排序中存在LMS子串相等的情况呢？递归处理lms子串的SA-IS结果即可。

然后我们只需要处理通过lms子串倒推所有串的关系。我们假设这部分和之前排序lms子串的部分复杂度都是F(n)

那么就有T(n)=T(n/2)+F(n)

代码:

原：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

void SA_IS(int n,int m,int *s,int *op,int *pos)
{
    int tot=0,cnt=0;int *S=s+n;//为了减少常数，这里直接取一段没有用过的地址而不是重新申请。
    op[n]=0;//为了方便，钦定最后一位是S型
    for(re int i=n-1;i;i--) op[i]=(s[i]!=s[i+1])?s[i]>s[i+1]:op[i+1];//O(n)求op
    rk[1]=0;
    for(re int i=2;i<=n;i++)
    if(op[i-1]==1 && op[i]==0) pos[++tot]=i,rk[i]=tot;//求出所有lms子串的端点
    else rk[i]=0;
    sa_sort(pos,n,m,s,op,tot);//排序lms子串。具体实现在后面
    int u=0,p=0;
    for(re int i=1;i<=n;i++)//去重，即unique
    if(rk[sa[i]])
    {
        u=rk[sa[i]];
        if(cnt<=1 || pos[u+1]-pos[u]!=pos[p+1]-pos[p]) ++cnt;//一个减小常数的优化：如果两个lms子串长度不一样，一定不同
        else
        {
            for(re int j=0;j<=pos[u+1]-pos[u];j++)//暴力判断。注意这里如果某个字符对应的lms后缀不同，也应当认为不同，因为如果首字母相同，L型后缀字典序一定大于S型。
            if(s[pos[u]+j]!=s[pos[p]+j] || op[pos[u]+j]!=op[pos[p]+j]){++cnt;break;}//因为lms子串总长度不超过 $O(n)$，所以暴力扫描复杂度是对的。
        }
        S[u]=cnt;//重新标号。
        p=u;
    }
    if(tot!=cnt) SA_IS(tot,cnt,S,op+n,pos+n);//cnt相当于不同数字个数，如果cnt==tot相当于所有数字两两相同，直接桶排序。为了方便，op和pos也直接取一段没有用过的地址。
    else for(re int i=1;i<=tot;i++) sa[S[i]]=i;
    for(re int i=1;i<=tot;i++) S[i]=pos[sa[i]];//得到真正的排名（之前的标号排的是lms子串，这里的排名是lms后缀）。
    sa_sort(S,n,m,s,op,tot);//利用lms子串得到真正的sa。
}

菜鸡的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void SA_IS(int n,int m,int *s,int *tp,int *pos)
{
	int tot=0,cnt=0;int *S=s+n;//为了减小常数，这里直接取一段没有用过的地址而不是重新申请。
	tp[n]=0;//为了方便，钦定最后一位是S型
	L(i,1,n-1) tp[i]=(s[i]!=s[i+1])?s[i]>s[i+1]:tp[i+1];
	rk[1]=0;
	R(i,2,n) if(tp[i-1]==1&&!tp[i]) pos[++tot]=i,rk[i]=tot;else rk[i]=0;//求出所有LMS子串的端点
	SA_sort(pos,n,m,s,tp,tot);//排序LMS子串
	int u=0,p=0;
	R(i,1,n) if(rk[sa[i]]) //去重，即unique
	{
		u=rk[sa[i]];
		if(cnt<=1||pos[u+1]-pos[u]!=pos[p+1]-pos[p]) ++cnt;//一个减小常数的优化：如果两个LMS子串长度不一样，显然这两个子串不同
		else
		{
			R(j,0,pos[u+1]-pos[u]) //暴力判断，注意这里如果某个字符对应的LMS后缀不同，也应当认为不同，因为如果首字母相同，L型后缀字典序一定大于S型
			if(s[pos[u]+j]!=s[pos[p]+j]||tp[pos[u]+j]!=tp[pos[p]+j]) {++cnt;break;}//因为LMS子串长度不超过$O(N)$，所以暴力扫描复杂度是对的。
		}
		S[u]=cnt;//重新标号
		p=u;
	} 
	if(tot!=cnt) SA_IS(tot,cnt,S,tp+n,pos+n);//cnt相当于不相同数字个数，如果cnt==tot相当于所有数字两两不同，直接桶排序。为了方便，tp和pos也直接取一段没有用过的地址。
	else R(i,1,tot) sa[S[i]]=i;
	R(i,1,tot) S[i]=pos[sa[i]];//得到真正的排名（之前的标号排的是LMS子串，这里的排名是LMS后缀）。
	SA_sort(S,n,m,s,tp,tot);////利用LMS子串得到真正的sa。
}

为了方便考虑第二次，即通过LMS子串的后缀数组倒推所有串的后缀数组。

我们把每个LMS子串左侧部分看做是一条链，也就是说现在有若干个已知递增的序列，要归并成一个完整序列，且数字大小不超过字典序。这本质上就是多路归并。

举个例子比如字符串aabcabbacacacaa

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a a b c a b b a c  a  c  a  c  a  a  #
S S S L S L L S L  S  L  S  L  L  L  S
        *     *    *     *           *

#                *|
a#                |
aa#               |
aabcabbacacacaa#  |
abbacacacaa#     *|
abcabbacacacaa#   |
acaa#            *|
acacaa#          *|
acacacaa#        *|
bacacacaa#        |
bbacacacaa#       |
bcabbacacacaa#    |
caa#              |
cabbacacacaa#     |
cacaa#            |
cacacaa#          |

首先先随便钦定一个位置。这个位置必须满足符合首字母的区间以及LMS子串的相对位置。

比如abbacacacaa#子串可以放在2,3,4,5,6位置但是不能放在1，因为1的首字母不是a

而acaa#可以放在3,4,5,6,7位置，但是一定要放在abbacacacaa#之后

这里采用一种比较方便的钦定方式：倒序放入区间末尾

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#                *| #
a#                |
aa#               |
aabcabbacacacaa#  |
abbacacacaa#     *|
abcabbacacacaa#   | abbacacacaa#
acaa#            *| acaa#
acacaa#          *| acacaa#
acacacaa#        *| acacacaa#
bacacacaa#        |
bbacacacaa#       |
bcabbacacacaa#    |
caa#              |
cabbacacacaa#     |
cacaa#            |
cacacaa#          |

然后我们先处理出所有L型后缀，我们考虑用已知的SA去推未知的。

具体来说，当前SA位置上有少数已经排好序的点，其余全是0

我们从左往右按顺序找到一个已经排好序且存在前缀的点SAi，我们想插入的后缀是SAi−1

首先这个操作前提是SAi−1是一个L型后缀。然后可以发现，因为是"在开头加上一个字符"，当前处理的这个串是以这个串首字母为开头且未被放入的串中最大的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#                *| #              <-#  <=i
a#                | a#             <-a  <=sa[i]-1
aa#               |                
aabcabbacacacaa#  |                
abbacacacaa#     *|                
abcabbacacacaa#   | abbacacacaa#   
acaa#            *| acaa#          
acacaa#          *| acacaa#        
acacacaa#        *| acacacaa#      
bacacacaa#        |                <-b
bbacacacaa#       |                
bcabbacacacaa#    |                
caa#              |                <-c
cabbacacacaa#     |                
cacaa#            |                
cacacaa#          |

首先所以指针都移到最开头。

当前i=1，那么下一个就是a#。直接赋值给a指针对应位置，然后a指针下移一位。

然后对于串a#，下一项是aa#，同样移动。

然后处理完所有L型后变成

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#                *| #              
a#                | a#             
aa#               | aa#            
aabcabbacacacaa#  |                
abbacacacaa#     *|                
abcabbacacacaa#   | abbacacacaa#   <-a
acaa#            *| acaa#          
acacaa#          *| acacaa#        
acacacaa#        *| acacacaa#      
bacacacaa#        | bacacacaa#     
bbacacacaa#       |                <-b
bcabbacacacaa#    | bcabbacacacaa# 
caa#              | caa#           
cabbacacacaa#     | cabbacacacaa#  
cacaa#            | cacaa#         
cacacaa#          | cacacaa#       
                  |                <-c

然后我们恢复所有指针位置，对应到最末尾

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#                *| #              
a#                | a#             
aa#               | aa#            
aabcabbacacacaa#  |                
abbacacacaa#     *|                
abcabbacacacaa#   | abbacacacaa#   
acaa#            *| acaa#          
acacaa#          *| acacaa#        
acacacaa#        *| acacacaa#      <-a <=sa[i]-1
bacacacaa#        | bacacacaa#     
bbacacacaa#       |                
bcabbacacacaa#    | bcabbacacacaa# <-b
caa#              | caa#           
cabbacacacaa#     | cabbacacacaa#  
cacaa#            | cacaa#         
cacacaa#          | cacacaa#       <-c <=i

然后我们需要从后往前所有S型后缀的部分。同L型后缀，这样所有处理的后缀都是同字符开头且当前未添加的后缀中最大的。

我们发现一点：cacacaa#的上一个前缀是acacacaa#。其实直接赋值就可以了。

然后按顺序处理：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#                *| #              
a#                | a#             
aa#               | aa#            
aabcabbacacacaa#  |                
abbacacacaa#     *|                
abcabbacacacaa#   | abbacacacaa#   <-a <=sa[i]-1
acaa#            *| acaa#          
acacaa#          *| acacaa#        
acacacaa#        *| acacacaa#      
bacacacaa#        | bacacacaa#     
bbacacacaa#       | bbacacacaa#    <-b
bcabbacacacaa#    | bcabbacacacaa#     <=i
caa#              | caa#           
cabbacacacaa#     | cabbacacacaa#  
cacaa#            | cacaa#         
cacacaa#          | cacacaa#       <-c

这时可以发现当前位置出问题了，之前的后缀与当前要放的不符（左边一列就是后缀数组）。也就是说我们一开始的钦定出问题了。

这时候我们直接赋值即可。为什么？因为这个值一定会被下一个后缀所更新掉。

所以说，一开始的赋值只要相对位置没有问题，所在区间没有问题，最后都能得到结果。

最终数组就如左边一列所示。

然后对于LMS子串的排序呢？这个好像是乱序的啊。

这里给出结论：我们可以直接按上述方式排序。

一遍排序（L型后缀）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

a a b c a b b a c a c a c a a #
S S S L S L L S L S L S L L L S
        *     *   *   *       *

#                *| #              <-#
a#                | a#             <-a
aa#               | aa#            
aabcabbacacacaa#  |                
abbacacacaa#     *|                
abcabbacacacaa#   | abbacacacaa#   
acaa#            *| acacacaa#      
acacaa#          *| acacaa#        
acacacaa#        *| acaa#          
bacacacaa#        | bacacacaa#     
bbacacacaa#       | bbacacacaa#    
bcabbacacacaa#    |                <-b
caa#              | caa#           
cabbacacacaa#     | cabbacacacaa#  
cacaa#            | cacacaa#       
cacacaa#          | cacaa#         
                  |                <-c

最终排序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#                *| #                *
a#                | a#               
aa#               | aa#              
aabcabbacacacaa#  | aabcabbacacacaa# 
abbacacacaa#     *| abbacacacaa#     *
abcabbacacacaa#   | abcabbacacacaa#  
acaa#            *| acaa#            *
acacaa#          *| acacacaa#        *
acacacaa#        *| acacaa#          *
bacacacaa#        | bacacacaa#       
bbacacacaa#       | bbacacacaa#      
bcabbacacacaa#    | bcabbacacacaa#   
caa#              | caa#             
cabbacacacaa#     | cabbacacacaa#    
cacaa#            | cacacaa#         
cacacaa#          | cacaa#

上面右排带*的就是排序后所有LMS子串的对应位置。

但是8和10是不是错了啊！

注意我们排的并不是后缀，而是一个子串。而[8,10]和[10,12]是本质相同的，所以怎么排都不算错。

对于正确性，一个感性的理解就是：如果一个串a>b且a排在b前，那么a通过一系列L和S后将会把b排到自己前面。

然后回到上例，这里[8,10]和[10,12]本质相同，所以最后去重时发现不是两两相同的，递归处理。

那么递归处理的串就是24431。

处理结束后返回的是25431。

然后根据上面的过程诱导排序即可。

总复杂度O(n)。

完整代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000010
#define re register
using namespace std;
char str[N];
int sa[N],rk[N],h[N],s[N<<1],op[N<<1],pos[N<<1],c1[N],c[N];
#define L(x) sa[c[s[x]]--]=x
#define R(x) sa[c[s[x]]++]=x
inline void sa_sort(int *S,int n,int m,int *s,int *op,int tn)
{
    for(re int i=1;i<=n;i++) sa[i]=0;
    for(re int i=1;i<=m;i++) c1[i]=0;
    for(re int i=1;i<=n;i++) c1[s[i]]++;
    for(re int i=2;i<=m;i++) c1[i]+=c1[i-1];
    for(re int i=1;i<=m;i++) c[i]=c1[i];
    for(re int i=tn;i;i--) L(S[i]);
    for(re int i=1;i<=m+1;i++) c[i]=c1[i-1]+1;
    for(re int i=1;i<=n;i++)
    if(sa[i]>1 && op[sa[i]-1]) R(sa[i]-1);
    for(re int i=1;i<=m;i++) c[i]=c1[i];
    for(re int i=n;i;i--)
    if(sa[i]>1 && !op[sa[i]-1]) L(sa[i]-1);
}
void SA_IS(int n,int m,int *s,int *op,int *pos)
{
    int tot=0,cnt=0;int *S=s+n;
    op[n]=0;
    for(re int i=n-1;i;i--) op[i]=(s[i]!=s[i+1])?s[i]>s[i+1]:op[i+1];
    rk[1]=0;
    for(re int i=2;i<=n;i++)
    if(op[i-1]==1 && op[i]==0) pos[++tot]=i,rk[i]=tot;
    else rk[i]=0;
    sa_sort(pos,n,m,s,op,tot);
    int u=0,p=0;
    for(re int i=1;i<=n;i++)
    if(rk[sa[i]])
    {
        u=rk[sa[i]];
        if(cnt<=1 || pos[u+1]-pos[u]!=pos[p+1]-pos[p]) ++cnt;
        else
        {
            for(re int j=0;j<=pos[u+1]-pos[u];j++)
            if(s[pos[u]+j]!=s[pos[p]+j] || op[pos[u]+j]!=op[pos[p]+j]){++cnt;break;}
        }
        S[u]=cnt;
        p=u;
    }
    if(tot!=cnt) SA_IS(tot,cnt,S,op+n,pos+n);
    else for(re int i=1;i<=tot;i++) sa[S[i]]=i;
    for(re int i=1;i<=tot;i++) S[i]=pos[sa[i]];
    sa_sort(S,n,m,s,op,tot);
}
int ht[N];
void get_ht(int n)
{
	for(re int i=1;i<=n;i++) rk[sa[i]=sa[i+1]]=i;
	for(re int i=1,p=0;i<=n;ht[rk[i]]=p,i++)
	if(rk[i]!=1) for(p=p-!!p;sa[rk[i]-1]+p<=n && i+p<=n && s[i+p]==s[sa[rk[i]-1]+p];p++);
}
namespace IO
{
    char obuf[(1<<21)+1],st[11],*oS=obuf,*oT=obuf+(1<<21);
    void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
    void Put(char x){*oS++=x;if(oS==oT)Flush();}
    void write(int x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put(' ');}
}using namespace IO;
int main()
{
    int n;
    fread(str+1,1,100000,stdin),n=strlen(str+1);
    while(!isalpha(str[n])) --n;
    for(int i=1;i<=n;i++) s[i]=str[i]-'a'+2;
    s[++n]=1;
    SA_IS(n--,28,s,op,pos);
    get_ht(n);
    for(int i=1;i<=n;i++) write(sa[i]);Put('\n');
    for(int i=2;i<=n;i++) write(ht[i]);Flush();
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

#include<bits/stdc++.h>
#define ld long double
#define tset puts("qwq");
#define test puts("QAQ");
#define pb(a) push_back(a)
#define pii pair<int,int> 
#define mkp make_pair
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
//#define int long long
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define Swap(x,y) (x^=y^=x^=y)
template <typename T> bool ckmax(T &x, T y) { return x<y?x=y,true:false;}
template <typename T> bool ckmin(T &x, T y) { return x>y?x=y,true:false;}
using namespace std;
//const ll inf=0x7f7f7f7f7f7f7f3f;
const ll inf=(1ll<<60);
//const int inf=0x7f7f7f7f;
//const int mod=1e9+7;
const double Pi=acos(-1);
const int mod=998244353;
const double eps=1e-6;
inline int fpow(int a,int b=mod-2,int p=mod){int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
/*
const int qwq=2000010;
int F[qwq],inv[qwq],Finv[qwq];
void init_C()
{
    F[0]=Finv[0]=inv[1]=1;
    R(i,2,qwq-10) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    R(i,1,qwq-10) F[i]=1ll*(F[i-1]*i)%mod,Finv[i]=1ll*(Finv[i-1]*inv[i])%mod;
}

inline int C(int n,int m){ if(m<0||m>n||n<0) return 0;return 1ll*F[n]%mod*1ll*Finv[m]*1ll%mod*1ll*Finv[n-m]%mod;}
*/

//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
inline ll read()
{
    char c=getchar();ll x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;
    return x;
}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
/*
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);  
uniform_int_distribution<long long> dist(0, 10000000);  // ¸ø¶¨·¶Î§
printf("%lld ",dist(rand_num));
*/
const int N=2e6+10;
char str[N];
int n;
int s[N],sa[N],rk[N],tp[N],pos[N],c[N],c1[N];
#define del(x) sa[c[s[x]]--]=x
#define add(x) sa[c[s[x]]++]=x
void SA_sort(int *S,int n,int m,int *s,int *tp,int tot)
{
	clr(sa,n+2);clr(c1,m+2);
	R(i,1,n) c1[s[i]]++;
	R(i,2,m) c1[i]+=c1[i-1];
	cpy(c+1,c1+1,m+2);
	L(i,1,tot) del(S[i]);
	R(i,1,m+1) c[i]=c1[i-1]+1;
	R(i,1,n) if(sa[i]>1&&tp[sa[i]-1]) add(sa[i]-1);
	cpy(c+1,c1+1,m+2);
	L(i,1,n) if(sa[i]>1&&!tp[sa[i]-1]) del(sa[i]-1);
}
void SA_IS(int n,int m,int *s,int *tp,int *pos)
{
	int tot=0,cnt=0;int *S=s+n;//为了减小常数，这里直接取一段没有用过的地址而不是重新申请。
	tp[n]=0;//为了方便，钦定最后一位是S型
	L(i,1,n-1) tp[i]=(s[i]!=s[i+1])?s[i]>s[i+1]:tp[i+1];
	rk[1]=0;
	R(i,2,n) if(tp[i-1]==1&&!tp[i]) pos[++tot]=i,rk[i]=tot;else rk[i]=0;//求出所有LMS子串的端点
	SA_sort(pos,n,m,s,tp,tot);//排序LMS子串
	int u=0,p=0;
	R(i,1,n) if(rk[sa[i]]) //去重，即unique
	{
		u=rk[sa[i]];
		if(cnt<=1||pos[u+1]-pos[u]!=pos[p+1]-pos[p]) ++cnt;//一个减小常数的优化：如果两个LMS子串长度不一样，显然这两个子串不同
		else
		{
			R(j,0,pos[u+1]-pos[u]) //暴力判断，注意这里如果某个字符对应的LMS后缀不同，也应当认为不同，因为如果首字母相同，L型后缀字典序一定大于S型
			if(s[pos[u]+j]!=s[pos[p]+j]||tp[pos[u]+j]!=tp[pos[p]+j]) {++cnt;break;}//因为LMS子串长度不超过$O(N)$，所以暴力扫描复杂度是对的。
		}
		S[u]=cnt;//重新标号
		p=u;
	} 
	if(tot!=cnt) SA_IS(tot,cnt,S,tp+n,pos+n);//cnt相当于不相同数字个数，如果cnt==tot相当于所有数字两两不同，直接桶排序。为了方便，tp和pos也直接取一段没有用过的地址。
	else R(i,1,tot) sa[S[i]]=i;
	R(i,1,tot) S[i]=pos[sa[i]];//得到真正的排名（之前的标号排的是LMS子串，这里的排名是LMS后缀）。
	SA_sort(S,n,m,s,tp,tot);////利用LMS子串得到真正的sa。
}
int ht[N];
void get_ht(int n)
{
	R(i,1,n) rk[sa[i]=sa[i+1]]=i;
	int k=0;
	R(i,1,n)
	{
		if(k) --k;
		while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
		ht[rk[i]]=k;
	}
}
namespace IO
{
	char obuf[(1<<21)+1],st[11],*oS=obuf,*oT=obuf+(1<<21);
    void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
    void Put(char x){*oS++=x;if(oS==oT)Flush();}
    void write(int x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put(' ');}
}using namespace IO;

signed main()
{
	fread(str+1,1,100000,stdin);n=strlen(str+1);
	while(!isalpha(str[n])) --n;
	R(i,1,n) s[i]=str[i]-'a'+2;
	s[++n]=1;
	//writeln(n);R(i,1,n) writesp(s[i]);puts("");
	SA_IS(n--,28,s,tp,pos);
	get_ht(n);
    R(i,1,n) write(sa[i]);Put('\n');
    R(i,2,n) write(ht[i]);Flush();
	return 0;
}

附一道需要用的题（卡SAM）

DC3 :

不会

获取height数组

LCP(最长公共前缀)

S(i)表示从位置i开始的后缀

两个字符串S和T的LCP就是最大的x(x≤min(|S|,|T|))使得Si=Ti(∀1≤i≤x)。

这里使用LCP(i,j)表示S(i)和S(j)的最长公共前缀

lcp(i,j)表示lcp(i,j)表示后缀i和后缀j的最长公共前缀（的长度）。

height数组的定义

height[i]=lcp(sa[i],sa[i−1])，即第i名的后缀与它前一名的前缀的最长公共前缀。

height[1]可以视为0。

这里使用h[i]表示height[rk[i]]

接下来是一些性质以及证明

1.lcp(sa[i],sa[j])=min(lcp(sa[i],sa[k]),lcp(sa[k],sa[j]))

放个盗来的图(以aaaaabaaab为例，下面的数组是sa)

img

证明:

设I=S(sa[i]),J=S(sa[j]),K=S(sa[k]),p=min(lcp(sa[i],sa[k]),lcp(sa[k],sa[j]))。

则I与K的前p个字符相同，K与J的前p个字符相同。所以I和J至少有前p个字符相同

由p=min(lcp(sa[i],sa[k]),lcp(sa[k],sa[j]))，可知I与K第p+1个字符不相同，或者J与K的第p+1个字符不相同。

所以I和J最长公共前缀为p。

2.h[i]≥h[i−1]−1（重点）

对于h[i−1]≤1时显然成立。

考虑h[i−1]>1的情况：

设k为sa[rk[i−1]−1]。

则h[i−1]=LCP(i−1,k)

把S(i−1)和S(k)去掉首字母，得到S(i)和S(k+1)，可知

LCP(i,k+1)=LCP(i−1,k)−1=h[i−1]−1

同时k+1在sa一定在i的前面

img

S(k)之所以在S(i−1)的前面，就是在第LCP(i−1,k)+1的字符差异导致的。如上图灰框圈出的部分。

当去掉首字母后，因为h[i−1]>1，所以S(i)与S(k+1)还是会在同样它的地方有差异，rk[k+1]还是小于rk[i]，k+1在sa中一定排在i前面。

那么所以比i排名靠前的且LCP最大的一定是与i相邻的sa[rk[i]−1]。

则lcp(sa[rk[i]],sa[rk[i−1]])≥LCP(i,k+1)

height[rk[i]]≥h[i−1]−1

h[i]≥h[i−1]−1

3.lcp(sa[i],sa[j])=min(height[k])(∀k,i<k≤j)

证明：根据性质1

lcp(sa[i],sa[j])

=min(lcp(sa[i],sa[i+1]),lcp(sa[i+1],sa[j]))

=min(lcp(sa[i],sa[i+1]),lcp(sa[i+1],sa[i+2]),lcp(sa[i+2],sa[j]))

=min(lcp(sa[k],sa[k−1]))(∀k,i<k≤j)

=min(height[k])(∀k,i<k≤j)

代码:

1
2
3
4
5
6
7

int k=0;
R(i,1,n)
{
	if(k) --k;
	while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
	ht[rk[i]]=k;
}

一些应用

任意两个后缀的LCP

由性质3可知：

LCP(i,j)=min(height[k])(min(rk[i],rk[j])+1<k≤max(rk[i],rk[j]))

用ST表O(nlog⁡n)预处理，O(1)回答。

不同子串个数

求一个子串本质不同的子串个数。

子串就是后缀的前缀，所以可以枚举每个后缀，计算前缀总数，再减掉重复。

“前缀总数"为总子串个数为n×(n+1)2

如果按后缀排序的顺序枚举后缀，每次新增的子串就是除了与上一个后缀的LCP剩下的前缀。这些前缀一定是新增的，否则会破坏lcp(sa[i],sa[j])=min(height[i+1⋯j])的性质。只有这些前缀是新增的，因为LCP部分在枚举上一个前缀时计算过了。

（每个后缀的所有前缀构成了所有子串。对于某一个后缀S(i)的前缀，与前面重复的个数为height[rk[i]]。）

答案即为n×(n+1)2−∑i=1nheight[i]

最长公共子串

求多个字符串的最长公共子串。

把每个子串依次连接起来，每个串之间用一个特殊字符隔开。再给每个串的字染上颜色。构建后缀数组。

扫一遍sa数组，用尺取法获取尽可能小的区间[l,r]使sa[i](∀i,l≤i≤r)，能覆盖所有颜色，所有的min(heigt[i])(∀i,l<i≤r)的最大值即为答案。用单调队列维护达到O(∑len(S))

模式串出现次数

给定一些母串和模式串，求每个模式串在多少个母串里出现过。

把所有的串拼到一起建出SA，找到每个模式串p的“匹配区间”，即最大的区间[l,r]使所有的LCP(i,p)≥|p|。答案具有单调性可以ST表+二分。由于模式串之间可能有子串关系，统计时染个色，模式串不加入答案，做一个前缀和即可。

去重的话可以类似于HH的项链（主席树，离线+树状数组，莫队等)。

可重叠最长重复子串

max(height[i])

不可重叠最长重复子串

二分答案。找到所有满足min(height[i])≥mid(l≤i≤r)的区间（区间尽可能大），若max(sa[i])−min(sa[i])≥mid则答案可行。（二分目标串的长度|S|，将h数组划分成若干个LCP≥|S|的段，利用RMQ对每个段求其中出现的数最大和最小的下标，若这两个下标的距离满足条件，则一定有长度为|S|的字符串不重叠地出现了两次。）

[ABC141E] Who Says a Pun?

最长回文子串

枚举一下回文中心p，求出翻转过来之前的前缀p与后缀p的LCP更新答案。把串翻转过来接在后面使用ST表维护

最小表示法

P4051 [JSOI2007]字符加密

题意：

给定一个串，可以任意把最后面的字符移到开头，求能得到的字典序最小的串。

题解：

把原串复制一遍接在后面（不加特殊字符），两边染个色。找到染前半段颜色的rk最小的后缀就是答案。

出现至少 k 次的子串的最大长度

「USACO06DEC」Milk Patterns

题解：

出现至少k次意味着后缀排序后有至少连续k个后缀的LCP是这个子串。

所以，求出每相邻k−1个height的最小值，再求这些最小值的最大值就是答案。

可以使用单调队列O(n)解决。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

signed main()
{
	n=read(),k=read();
	R(i,1,n) a[i]=b[i]=read();
	sort(b+1,b+n+1);
	int tit=unique(b+1,b+n+1)-b-1;
	R(i,1,n) a[i]=lower_bound(b+1,b+tit+1,a[i])-b;
	get_SA(a,sa,rk,n,ht);
	R(i,1,n)
	{
		while((int)q.size()>0&&q.front()<=i-k+1) q.pop_front();
		while((int)q.size()>0&&ht[q.back()]>=ht[i]) q.pop_back();
		q.pb(i);
		if(i>=k-1&&(int)q.size()>0) ckmax(ans,ht[q.front()]);
	}
	writeln(ans);
}

寻找最小的循环移动位置

「JSOI2007」字符加密

将字符串S复制一份变成SS就转化成了后缀排序问题。

在字符串中找子串

在线地在主串T中寻找模式串S。

我们可以先构造出T的后缀数组，然后查找子串S。若子串S在T中出现，它必定是T的一些后缀的前缀。因为我们已经将所以后缀排序了，我们可以通过在p数组中二分S来实现。比较子串和当前后缀的时间复杂度为O(|S|)，因此找子串的时间复杂度为O(|S|log⁡|T|)。注意，如果该子串在T出现多次，每次都是在p数组中相邻的。因此出现次数可以通过再次二分找到，输出每次出现的位置也很轻松。

从字符串首尾取字符最小化字典序

「USACO07DEC」Best Cow Line

题目大意：

给你一个字符串，每次从首或尾取一个字符组成字符串，问所有能够组成的字符串中字典序最小的一个。

题解：

暴力做法就是每次最坏O(n)地判断当前应该取首还是尾（即比较取首得到的字符串与取尾得到的反串的大小），只需优化这一判断过程即可。

由于需要在原串后缀与反串后缀构成的集合内比较大小，可以将反串拼接在原串后，并在中间加上一个没出现过的字符(如#，代码中可以直接使用空字符)，求后缀数组，即可O(1)完成判断

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

signed main()
{
	n=read();int l=1,r=n;
	R(i,1,n) while(!isalpha(s[i]=getchar()));
	R(i,1,n) ss[i]=ss[2*n+2-i]=s[i];
	n=2*n+1;
	get_SA(ss,sa,rk,n);
	while(l<=r) 
	{
		++tit;
		printf("%c",rk[l]<rk[n+1-r]?s[l++]:s[r--]);
		if(tit%80==0) puts("");
	}
}

连续的若干个相同子串

我们可以枚举连续串的长度|S|，按照|S|对整个进行分块，对相邻两块的块首进行LCP与LCS查询，具体见[2009]后缀数组——处理字符串的有力工具。

结合并查集

某些题目求解时要求你将后缀数组划分成若干个连续 LCP 长度大于等于某一值的段，亦即将h数组划分成若干个连续最小值大于等于某一值的段并统计每一段的答案。如果有多次询问，我们可以将询问离线。观察到当给定值单调递减的时候，满足条件的区间个数总是越来越少，而新区间都是两个或多个原区间相连所得，且新区间中不包含在原区间内的部分的h值都为减少到的这个值。我们只需要维护一个并查集，每次合并相邻的两个区间，并维护统计信息即可。

经典题目：「NOI2015」品酒大会。

结合线段树

某些题目让你求满足条件的前若干个数，而这些数又在后缀排序中的一个区间内。这时我们可以用归并排序的性质来合并两个结点的信息，利用线段树维护和查询区间答案。

结合单调栈

例题：「AHOI2013」差异

由于直接算答案不是很好做，考虑先求出∑1≤i<j≤nlen(Ti)+len(Tj)再减去后面那堆东西。

这部分答案为n(n−1)(n+1)2（每个后缀都出现了n−1次，后缀总长是n(n+1)2）

之后考虑怎么搞lcp(i,j)这项，我们知道lcp(i,j)=k等价于Missing or unrecognized delimiter for \left

所以可以将lcp(i,j)记作Missing or unrecognized delimiter for \left对答案的贡献。

考虑每个位置对答案的贡献是哪些后缀的LCP，其实就是从它开始向左若干个连续的height大于它的后缀选一个，再从向右若干个连续个height不小于它的后缀中选一个。这个东西可以单调栈搞。

虽然写的时候偷懒直接搞了个悬线法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

signed main()
{
	scanf("%s",str+1);
	n=strlen(str+1);ans=1ll*(n+1)*n*(n-1)/2;
	R(i,1,n) s[i]=str[i]-'a'+2;
	get_SA(s,sa,rk,n),get_ht(n,ht);ht[n+1]=-1;
	R(i,1,n) l[i]=r[i]=i;
	R(i,1,n) while(ht[l[i]-1]>ht[i]) l[i]=l[l[i]-1];
	L(i,1,n) while(ht[r[i]+1]>=ht[i]) r[i]=r[r[i]+1];
	R(i,1,n) ans-=2ll*ht[i]*(i-l[i]+1)*(r[i]-i+1);
	//L(i,1,n) printf("%lld %lld %lld %lld\n",i,i-l[i]+1,r[i]-i+1,ht[i]);
	printf("%lld\n",ans);
}

习题