柒葉灬 的博客

柒葉灬 的博客

后缀数组(个人笔记)

posted on 2019-03-22 20:42:42 | under 专题总结 |

后缀数组SA 总结


后缀数组就是把长度为n的字符串分成n个后缀

并把这n个后缀按字典序排序

最后通过一个height数组实现字符串各种应用


模板

void radix_sort(){
    for(int i=0;i<=M;i++)cnt[i]=0;
    for(int i=1;i<=n;i++)cnt[Rank[i]]++;
    for(int i=1;i<=M;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)SA[cnt[Rank[tp[i]]]--]=tp[i];
}
void suffix_sort(){
    M=200;
    Rank[n+1]=0;
    for(int i=1;i<=n;i++){
        Rank[i]=str[i];
        tp[i]=i;
    }
    radix_sort();
    for(int w=1,p=0;p<n;w<<=1){
        p=0;
        for(int i=1;i<=w;i++)
            tp[++p]=n-w+i;
        for(int i=1;i<=n;i++)
            if(SA[i]>w)tp[++p]=SA[i]-w;
        radix_sort();
        memcpy(tp,Rank,sizeof(Rank));
        Rank[SA[1]]=p=1;
        for(int i=2;i<=n;i++){
            Rank[SA[i]]=(tp[SA[i]]==tp[SA[i-1]]&&tp[SA[i]+w]==tp[SA[i-1]+w]?p:++p);
        }
        M=p;
    }
}
void GetHeight(){
    int k=0;
    for(int i=1;i<=n;i++){
        if(k)k--;
        int j=SA[Rank[i]-1];
        while(i+k<=n&&j+k<=n&&str[i+k]==str[j+k])k++;
        height[Rank[i]]=k;
    }
}

有几个关于后缀数组实现的问题说一下

for(int i=2;i<=n;i++){
    Rank[SA[i]]=(tp[SA[i]]==tp[SA[i-1]]&&tp[SA[i]+w]==tp[SA[i-1]+w]?p:++p);
}

这段代码里面, $SA[i]+w$ 会不会超过 $n$ 呢?

答案是会的,

例如在字符串 $"abab"$ 当中,

在比较前面的 $"ab"$ 和后面一个 $"ab"$ 的时候

由于相同,会继续比较 $SA[i]+w$ ,

此时就会访问到大于 $n$ 的位置。

那么,会不会访问到很远呢?

答案是不会的,

$SA[i]+w$ 最多只有 $n+1$ ,原因很简单,

因为如果 $SA[i]+w>n+1$ 的时候,

$tp[SA[i]]==tp[SA[i-1]]$ 肯定不成立,

因为比较的字符串长度都不一样。

所以说,如果多case,只要Rank[n+1]=0即可。


后缀数组能解决的经典问题

eg:求两个后缀的最长公共前缀(lcp)。

显然最长公共前缀是二者之间高度数组的最小值。

可以用 $ST$ 表维护。

(网上有O(n)的标准 $rmq$ 算法)

专题B

题意:求一个最长长度的子串,使得在原串当中出现了 $K$ 次(可以重叠)。

思路:二分长度,然后扫一遍高度数组,判断是否存在这样的子串。


专题C

题意:求一个串当中有多少个不同的子串。

思路:子串一定是后缀的前缀,所以只要扫一遍高度数组,把重复的前缀减掉即可。


专题D

题意:求一个串当中最长的回文串,如果有多个,输出第一个。

思路:把串倒过来接在原串后面,用一个"#"连接,然后枚举中点(注意长度可以是偶数),求两个串的LCP即可。


专题F

题意:求最多连续出现的子串,即"ababab"是"ab"出现了3次。

思路:枚举子串的长度K,如果有这种子串,他一定会在{str[1],str[1+k],str[1+2*k]...}中相邻两个出现,然后找他们向前向后分别能最远匹配多远。(注意还要判一下字典序!)


更多的内容可以看国家队论文。

更多的好题目尽在专题里面