周报

后缀数组

2020年3月24日

前置知识

  • 桶思想
  • 倍增思想

*桶思想：空间换时间

*应用：基数排序、计数排序、哈希表……

◈计数排序

某大厂面试题：知道高考分数，如何快速确定省内排名？

答：统计一下有多少人考得比我高

以江苏高考为例，江苏高考满分是470，一般分数都是在300~400之间，相差不会很大。这时，我们只要开一个以分数范围为索引的数组buk，扫一遍所有人的成绩，假设当前扫到的人分数是i，只要递增buk[i] 即可，最后把所有索引大于你分数的bucket相加，就可以在O（n）的时间复杂度内知道你的排名。

而基数排序呢，我的理解就是有顺序地进行多次计数排序（求sa会用到基数排序）

*倍增思想：每次将考虑的范围扩大或减少一倍从而达到加速的效果，将某一步的O(n)优化到O(logn)也就是一种自底向上的二分

*应用：快速幂、ST表等

算法思想和模板

我们先来讨论几个哲学问题：
1、sa是谁（自己百度）

2、sa从何而来（百度 Udi Manber & Gene Myers《Suffix arrays: a new method for on-line string searches》和后缀数 ）

3、sa要到哪里去

咳，关于问题3其实我想说的是：sa有啥用。

字符串有一个很重要的性质：它的每个子串一定是某个后缀的前缀。这样我们只要再求一个前缀相关的数组（height）就可以解决大多数字符串问题啦！

sa到哪里去？去和前缀愉快地玩耍~

搞明白了这些以后应该对sa有了一个比较简单的了解。那我们咋求呢？

先考虑暴力算法：

1、枚举字串的每一个后缀( O(n) )

2、后缀之间相互比较

 最后复杂度O（n^2)

如何优化？有两个比较常用的算法：倍增和DC3。这里只讲倍增（DC3我不会啊）

暴力为啥慢，因为存在大量的重复比较

倍增优化的思路：

1、开始时将字符串的每一个字符看作一个子串，对其排名（眼不眼熟？单关键字的排序？计数排序！）

2、字符串的长度扩大到原来的两倍，以上一次排名中该子串的rank为第一关键字，和它后一个子串的rank为第二关键字，基数排序

3、当子字符串长度扩大到大于等于原串的时候，便相当于所有的后缀，此时的rank即为所求。

这样就van事了吗？当然没有，觉得van事的请往上翻。

还要求一个height数组，同样暴力O（n^2)

我们引入一个h数组：

定 义：

h[i]=height[rank[i]]

即suffix(i)和在它前一名的后缀的最长公共前缀

h 数组有以下性质：

h[i]≥h[i-1]-1

证明：

设 suffix(k)是排在 suffix(i-1)前一名的后缀，则它们的最长公共前缀是

h[i-1]。那么 suffix(k+1)将排在 suffix(i)的前面（这里要求 h[i-1]>1，如果

h[i-1]≤1，原式显然成立）并且 suffix(k+1)和 suffix(i)的最长公共前缀是

h[i-1]-1，所以 suffix(i)和在它前一名的后缀的最长公共前缀至少是 h[i-1]

1。按照 h[1],h[2],……,h[n]的顺序计算,并利用 h 数组的性质，时间复杂度可

以降为 O(n)。

——IOI2009 国家集训队论文 后缀数组 罗穗骞

上代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
using namespace std;
int sa[MAXN], rak[MAXN], height[MAXN], buk[MAXN], tp[MAXN], a[MAXN], n, m; 
char str[MAXN];
void Rsort(int *rak,int *tp){
    for(int i=0; i<=m; ++i) buk[i]=0;
    for(int i=1; i<=n; ++i) buk[rak[tp[i]]]++;
    for(int i=1; i<=m; ++i) buk[i]+=buk[i-1];
    for(int i=n; i>=1; --i) sa[buk[rak[tp[i]]]--]=tp[i];
}
int Cmp(int *f,int x,int y,int w){
    return f[x]==f[y]&&f[x+w]==f[y+w];
}
void Getsa(){
    for(int i=1; i<=n; ++i)rak[i]=a[i],tp[i]=i;
    m=127 ,Rsort(rak,tp);
    for(int w=1,p=1,i; p<n; w+=w,m=p){
        for(p=0,i=n-w+1; i<=n; ++i)
            tp[++p]=i;
        for(i=1; i<=n; ++i) 
            if(sa[i]>w) tp[++p]=sa[i]-w;
        Rsort(rak,tp);
        swap (rak,tp);
        rak[sa[1]]=p=1;
        for(i=2; i<=n; ++i)
            rak[sa[i]]= Cmp(tp,sa[i],sa[i-1],w) ? p : ++p;
    }
    int j,k=0;
    for(int i=1; i<=n; height[rak[i++]]=k)
        for(k=k?k-1:k,j=sa[rak[i]-1]; a[i+k]==a[j+k]; ++k);
}
void Init(){
    scanf("%s",str);
    n = strlen(str);
    for(int i=0; i<n; ++i) a[i+1] = str[i];
}
int main(){
    Init();
    Getsa();
    int ans = height[2];
    for(int i=3;i<=n;++i) ans += max(height[i] - height[i-1], 0);
    printf("%d\n", ans);    
}

p.s.我觉得比较重要的是对以下四个数组的理解：（搞清楚数组本身表示什么，数组下标表示什么）敲黑板划重点

SA[i] :         满足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]],即排名为i的后缀为Suffix[SA[i]]

Rank[i] :     Suffix[i]在所有后缀中的排名(与Rank是互逆运算)

Height[i] : 表示Suffix[SA[i]]和Suffix[SA[i – 1]]的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀

H[i] :          等于Height[Rank[i]]，也就是后缀Suffix[i]和它前一名的后缀的最长公共前缀

应用和例题

有空再更，嗯……大概……

Views: 99

2条评论

发表评论