后缀数组

后缀数组(suffix array)详解 - 北岛知寒 - 博客园 (cnblogs.com)

前置知识

子串

　　字符串S的子串r[i..j]，i<=j，表示S串中从i到j这一段，就是顺次排列r[i],r[i+1],...,r[j]形成的子串。

后缀

　　后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为Suffix(i)，

也就是Suffix(i)=S[i...len(S)-1] 。

后缀数组(SA[i]存放排名第i大的后缀首字符下标)

　　后缀数组 SA 是一个一维数组，它保存1..n 的某个排列SA[1] ，SA[2] ，...,SA[n] ，

　　并且保证Suffix(SA[i])<Suffix(SA[i+1])， 1<=i<n 。

也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。

名次数组（rank[i]存放suffix(i)的优先级）

　　名次数组 Rank[i] 保存的是 Suffix(i) 在所有后缀中从小到大排列的“名次”

img
img 
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
理解为sa[i]就是第i小的那个字符串起始的那个位置

rank[i]就是i起始的字母排名第rank[i]小

后缀数组和名次数组为互逆运算。
SA[i] = j表示为按照从小到大排名为i的后缀  是以j（下标）开头的后缀

rank[i] = j 表示为按照从小到大排名  以i为下标开始的后缀  排名为j
RANK表示你排第几   SA表示排第几的是谁

rank[sa[i]]=i

height数组：height[i]保存的是suffix(i)和suffix(i-1)的最长公共前缀的长度。也就是排名相邻的两个后缀的最长公共前缀。

构造sa数组的方法有2种：

1)倍增算法：O(nlongn)

2)DC3算法：O(n)

倍增算法：

一轮一轮比较，

设substr(i,len)从第i个字符开始，长度为len的字符串，我们可以把第k轮substr(i,2^k)看出（i,2^k-1)和substr(i+2^k-1,2^k-1)拼起来的东西。
这样就变成上一轮遇到的了，于是变成了一个两位数排序，这样就可以变成一个一位数排序继续比较喽。
于是我们需要基数排序
基数排序(对于两位数的数复杂度就是O(Len)的)。

就像一个两位数的比较

后缀数组 最详细讲解 - victorique - 博客园 (cnblogs.com)

盗窃一下这位大师的图，先orz奉上

havana1

倍增过程

初始化

首先对字符串 $ s $ 的所有长度为 1 的子串（即每个字符）进行排序，得到排序后的编号数组 $ _1 $ 和排名数组 $ _1 $。

倍增步骤

  1. 长度为 2 的子串
    • 用两个长度为 1 的子串的排名，即 $ _1[i] $ 和 $ _1[i+1] $，作为排序的第一、第二关键字。
    • 对字符串 $ s $ 的每个长度为 2 的子串：
      $ {s[i (i+1, n)]  |  i } $
      进行排序，得到 $ _2 $ 和 $ _2 $。
  2. 长度为 4 的子串
    • 用两个长度为 2 的子串的排名，即 $ _2[i] $ 和 $ _2[i+2] $，作为排序的第一、第二关键字。
    • 对字符串 $ s $ 的每个长度为 4 的子串：
      $ {s[i (i+3, n)]  |  i } $
      进行排序，得到 $ _4 $ 和 $ _4 $。
  3. 一般情况
    • 用长度为 $ $ 的子串的排名，即 $ {w/2}[i] $ 和 $ {w/2}[i+w/2] $，作为排序的第一、第二关键字。
    • 对字符串 $ s $ 的每个长度为 $ w $ 的子串：
      $ s[i (i+w-1, n)] $
      进行排序，得到 $ _w $ 和 $ _w $。
    • 其中，当 $ i+w > n $ 时，视 $ _w[i+w] $ 为无穷小。
    • 最终，当 $ w n $ 时，得到的编号数组 $ _w $ 就是后缀数组。

时间复杂度分析

  1. 倍增次数
    • 倍增的过程是 $ O(n) $，因为每次长度翻倍，最终不超过字符串长度 $ n $。
  2. 排序复杂度
    • 每次倍增使用 sort 对子串进行排序，复杂度为 $ O(n n) $。
    • 每次排序中，子串的比较花费 $ 2 $ 次字符比较。
  3. 更新排名
    • 每次倍增后，需要 $ O(n) $ 时间更新排名 $ $。
    • 相较于 $ O(n n) $ 的排序复杂度，可以忽略不计。

综合来看，算法的时间复杂度为： $ O(n ^2 n) $

优化方向

如果能够实现 $ O(n) $ 的排序，那么可以在 $ O(n n) $ 的时间内计算后缀数组。

基数排序

假设有一堆3位数

先按照个位数扔进去桶

再依次从左到右出来

然后按照十位数一个个扔进去桶

再依次从左到右出来

再百位

最后出来的一定是有序的。

又到了经典的大眼瞪小眼环节（）

完整代码：

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[10001000];
//在定义数组的时候，有一个小细节，这里的y[]必须开两倍大小
int b[7501000],x[7501000],y[7501000],sa[7501000];
void SA(){
    int num;
    for(int i = 0;i<n;i++)b[x[i]=s[i]]++;
    for(int i = 1;i<=m;i++)b[i]+=b[i-1];
    for(int i = n-1;i>=0;i--)sa[--b[x[i]]]=i;
    /*
我们要先根据第一位排序，确定最初的 sa,
我们用x[i]表示第一关键字。
b数组是桶，这里用到的就是桶排序的思想，来统计每种字符有多少种。
为了方便标号，就先做一个前缀和。这样字典序越大，所对应的的 b越大。
sa[i]表示排名为i的后缀编号是什么，这里根据输出
此时为0 2 4 1 3
表示最小的由0也就是第一个a开始，最大的由3开始也就是第二个b开始
因为这句话，摆烂一下午（）
可调试代码
这里的意思主要是大的字母出现的次数多，然后就可以决定位置
因为sa[--b[x[i]]]其中的b[x[i]]就是大的字母的出现次数，如果是b毫无疑问就是3，4被承包了，然后记录下b出现的那两个位置，a也同理，因此
   for(int i=0;i<n;i++)
{
	cout<<sa[i]<<" ";
}
    */
    for(int k = 1;k<n;k*=2)
//利用倍增的思想：
	{
        num = 0;    
//y[i]表示排名为第 i 的第二关键字 ,也就是确定 x 的排列的东西。
        for(int i = n-k;i<n;i++)y[num++] = i;
        //因他们已经排序完了，后面不可能有数字，所以先存
        //就是说呢，这些数字啊，注定是无法再和后面的东西一起组成一个系列的，因为后面没有东西了啊，就比如说ababa，你让最后一个a找谁去结合成2个字母呢，自然就是没有办法，于是最后的下标就到前面去
        for(int i = 0;i<n;i++)if(sa[i]>=k)y[num++] = sa[i]-k;
        //这里也一个细节，此时第一个字母的相对关系我们已经知道了。那第二个字母的大小呢？我们还需要一次排序么？其实大可不必，因为我们忽略了一个非常重要的性质：第i+1个后缀的第一个字母，因此每个后缀的第二个字母的相关位置关系也是已经知道的
        /*
        好比如
        aabaaaab
        abaaab
        aaaab
        aaab
        aab
        ab
        baaaab
        b
        第二个字母的顺序不是也是显而易见，只是最后一个b被移到前面，其他都减去一罢了
        也就对应上面的减k
        比如第一轮的第一关键字的排列为
        1 2 3 5 6 7 3 8
        8 1 2 4 5 6  2 7
        这就是第一轮的第二关键字
        */
        for(int i = 0;i<=m;i++)b[i] = 0;
        //将b数组初始化
        for(int i = 0;i<n;i++)b[x[i]]++;
        //重新对x计数
        for(int i = 1;i<=m;i++)b[i]+=b[i-1];
        //累加，和上面很类似
        for(int i = n-1;i>=0;i--)sa[--b[x[y[i]]]]=y[i],y[i]=0;
        /*
        这部分代码的作用就是用结合两个关键字把总的排序搞出来
我们应该做的，就是先根据第一关键字排序，第一关键字相等时根据第二关键字大小排序。
但是看上去，只进行了一次计数排序啊。
还记得这个计数排序的特点：先根据x的值排序，x值相等时根据出现先后次序排序。
x里面存了上次关键字的排序，在本次排序中即是第一关键字的排序，x的值排序==第一关键字排序，这里的计数排序做的是对的。那么第二关键字呢？
前面对第二关键字进行了排序，在这里x[y[i]]就是根据第二关键字的顺序重新改变了第一关键字的顺序，也就是说在本次计数排序中，出现先后次序排序==第二关键字大小排序。
换句话说，我们先单独对第二关键字排序，根据这个顺序改变第一关键字的顺序，由于在计数排序时首先按照第一关键字的值排序，而第一关键字的值没有改变所以首先还是根据第一关键字排序，改变的是第一关键字相同的时候，出现在前面的第二关键字排在前面。
        */
        
	    swap(x,y);
        num = 0;
        x[sa[0]] = 0;
        for(int i = 1;i<n;i++)x[sa[i]] = (y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        /*
        每次新的迭代要用到rank数组x，由于有了刚求的关键字排序数组sa，要得到rank数组也很容易。但是对于相同的值，rank应该相同，所以要判断一下合并以后的关键字是否相同。
        */
        if(num==n)break;
        //如果能到Num，证明有完全相同的，这一轮没比出来结果
        m=num;
    }
    return;
}
int main(){
 cin>>s;
    n = strlen(s);
    //长度
    m = 128;
    //字母的范围
    SA();
    //输出
    for(int i = 0;i<n-1;i++){
   cout<<sa[i]+1<<' ';
    }
    cout<<sa[n-1]+1<<'\n';
    return 0;
}

LCP

image-20240221201420150
image-20240221201438506 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void LCP()
{	
    int k=0; //用k代表h[i]
    for(int i=1;i<=n;i++)rk[sa[i]]=i; //初始化rk[i]
    for(int i=1;i<=n;i++)//这里其实是枚举rk[i]
    {	
        if(rk[i]==1)continue; //height[1]=0
        if(k)k--; //h[i]>=h[i-1]-1,更新k然后一位位枚举
        int j=sa[rk[i]-1];//前一位字符串
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;//一位位枚举
        height[rk[i]]=k;//h[i]=height[rk[i]]
    }
    for(int i=1;i<=n;i++)
      cout<<height[i]<<' ';
    cout<<'\n';
}



  int ans=inf;//求LCP(x,y)
  for(int i=x+1;i<=y;i++)
  	ans=min(ans,height(i));
 cout<<ans<<'\n';