xrr 的博客

xrr 的博客

OI 从入门到入土

LCP (最长公共前缀)——后缀数组的延续

posted on 2018-07-17 15:36:53 | under 字符串算法 |

先提醒一下,本算法需要以后缀数组为知识前提,不会的走这里

后缀数组

然后,我们还要有一个前置知识就是RMQ,即求区间最值的算法,一般用ST倍增,不会的求助百度

我们在进行过后缀数组的排序后得到的是一个数组sa[ ]

它的含义是排名为其下标的后缀的起始位置是哪。

我们需要另一个数组与sa构成反函数。

它就是rank[ ]。

它的含义是以其下标为后缀起始位置的后缀的排名。。。

最后我们要一个LCP的结果数组,它就是height[ ]它的定义又是啥呢?

height[ i ]表示后缀排名为i与排名为i-1的最长公共前缀。由于排名是有序的,因此公共前缀越长其排名越靠近。

所以我们可以得出这样一个结论,排名为i的后缀与排名为j的后缀的最长公共前缀的大小等于height[ i+1 ],height[ i+2 ],height[ i+3 ] ...... height[ j ]中的最小值。

我们用上rank函数,就是后缀i与后缀j的最长公共前缀为height[ min(rank[ i ],rank[ j ])+1 ]到height[ max(rank[ i ],rank[ j ]) ]中的最小值。

那么我们就需要计算height[ ]然而如果根据定义,需要O(n)的时间复杂度来去一个的height,总时间复杂度就是O(n^2)

这里给出一个时间复杂度为O(n)的算法,他用h[ i ]=height[ rank[ i ] ]这个辅助数组做到了递推关系(虽然h[ ]在代码中并没有出现。。。orz)

给出一个性质

h[i]>=h[i-1]-1

是不是一脸懵逼?

因为对于后缀i-1来说,假设它与后缀k在sa中相邻

即rank[k]=rank[i-1]-1

所以,我们可以看到,i-1串删去头字符后变为i串

k删去头字符后变为k+1串。而i与k+1的公共前缀长为h[ i-1]-1,当然,i与k+1串不一定相邻,但可以肯定的是k+1串小于i串

由于公共前缀越长其排名越靠近,所以排名越靠近,公共前缀越长

所以i与小于i的第一个后缀子串的的公共前缀长一定不短于i与k的公共前缀长。

我们只要在这个长度上继续向后比较就行了。

看代码:

int rank[MAXN],height[MAXN];
void getheight(){
    int j,k=0;
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0;i<n;i++){
        if(k) k--;
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rank[i]]=k;
    }
}

先给rank赋值

然后就是对h[i]的递推过程

这里给出几个例题:

  1. life form

翻译后的

  1. 口吃的外星人(该题需要将哈希与LCP结合)

我在这里解释一下第一题

我们需要找出所有字符串中子串在各字符串中出现的次数超过n/2的最长子串的长度

我们先将这些字串拼接(字串中间插入几个不同的不出现的字符),然后将其分解为后缀数组,然后求出height,然后二分答案P,并根据P(在小于height[ ]小于p时)将其分段,然后判断是否有连续的超过n/2的段。

我们在判断的时候用flag[ i ]表示当前段中是否包含原串i,检查flag为1的个数是否超过n/2.然后清空flag数组(蓝书里写了还有不用清空flag的方法,也不用重新计算,有谁知道吗?)

蓝书还写可以缩到O(n),扫描一次height,并用上栈

LCP+后缀树の代码