后缀数组初探

前言：JSOI2017round2day2T1后缀数组模板题一点都没看出来。不然就翻盘了

　　痛定思痛后决定恶补字符串。

后缀数组

全是论文上抄来的。

学了一周，终于搞懂一些了。

1.基本定义

　　字符串S；

　　后缀：从位置i开始到结尾的子串，记作Suffix(i)=s[i..len[s]];

　　后缀数组sa[1..n]

　　表示1..n的一个排列，满足Suffix(sa[i])<Suffix(sa[i-1])

　　即：在所有后缀中排第i的是谁

　　名次数组rank[1..n]

　　表示Suffix(i)在后缀中的名次。

　　即：后缀i排第几。

　　所以sa与rank为逆运算。

2.倍增算法求后缀数组。

　　//学过DC3邪教的自行离开。其实我是用后缀自动机构造的。

　　算法非常好理解，就是用倍增求出每个字符开始长度为2^k的子字符串排序

　　k==0..log2n上取整， 最后一遍处理时，子串相当于后缀。

　　代码：

void suffix(){
    register int i,k;
    memset(cnt,0,sizeof(cnt));
    for (i=1;i<=l;i++)    cnt[s[i]]++;
    for (i=1;i<=MAXASCLL;i++)    cnt[i]+=cnt[i-1];
    for (i=l;i>0;i--) sa[cnt[s[i]]--]=i;
    rank[sa[1]]=1;
    for (i=2;i<=l;i++)    rank[sa[i]]=rank[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
    for (k=1;rank[sa[l]]<l;k*=2){
        for (i=1;i<=l;i++) x[i]=rank[i];
        for (i=1;i<=l;i++) y[i]=(i+k<=l)?rank[i+k]:0;//x为第一关键字，y为第二关键字
        memset(cnt,0,sizeof(cnt));
        for (i=1;i<=l;i++) cnt[y[i]]++;
        for (i=1;i<=l;i++) cnt[i]+=cnt[i-1];
        for (i=l;i>0;i--) say[cnt[y[i]]--]=i;
        memset(cnt,0,sizeof(cnt));
        for (i=1;i<=l;i++) cnt[x[i]]++;
        for (i=1;i<=l;i++) cnt[i]+=cnt[i-1];
        for (i=l;i>0;i--) sa[cnt[x[say[i]]]--]=say[i];//基数排序，先排y，再排x
        rank[sa[1]]=1;
        for (i=2;i<=l;i++) rank[sa[i]]=rank[sa[i-1]]+(x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]]);    
    }
}

 这里有个小优化：若rank[sa[n]]已经为n时（所有串已经分出大小），就退出。

时间复杂度：O(n log n);不要尝试跑1e6的构造数据（字符基本相同），常数巨大QAQ

3.height数组（最长公共前缀lcp）

　　学会了构造，就要用后缀数组搞事情了。

　　最经典的运用就是height数组。

　　定义height[i]=Suffix(sa[i])与Suffix(sa[i-1])的最长公共前缀。

　　对于Suffix(j),Suffix(k); rank[j]<rank[k];

　　他们的最长公共前缀为min(height[rank[j]+1]..height[rank[k]]);

　　毛想想，由于序列是升序的，那么数组的变换是不可逆(若sa[i],sa[i+1]的第j位发生了变化，那么sa[i],sa[i+1]的第j位(或以前的位)一定也变了)。

　　那么问题就是如何快速求出height数组了。

　　定义h[i]=height[rank[i]] Suffix(i)与前一名的最长公共前缀。

　　举个例子：

　　S=abaac

　　Suffix=abaac, baac, aac, ac, c

　　sa=3,1,4,2,5

　　rank=2,4,1,3,5

　　height=0,1,1,0,0

　　h=1,0,0,1,0

　　h数组有以下性质： h[i]>=h[i-1]+1;

　　证明：　设Suffix(k)是排在Suffix（i-1）前一名的后缀（rank[k]=rank[i-1]-1）

　　则它们的最长公共前缀为h[i-1],

　　若h[i-1]<2, 那么显然成立，当h[i-1]>=2时，S[i-1..i]==S[k..k+1],

　　且应为k在i-1的前一位，所以k+1排在i的前一位。

　　所以至少要共享后h[i-1]-1位

void makeheight(){
    register int i,k=0,j;
    for (i=1;i<=l;i++){
        k=(k>0)?k-1:0;
        if (rank[i]==1){
            height[rank[i]]=0; k=0;
            continue;
        }
        for (j=sa[rank[i]-1];(j+k<=l)&&(i+k<=l)&&(s[j+k]==s[i+k]);k++);
        height[rank[i]]=k;
    }
}

　　有了height数组，就可以用rmq求出lcp

　　例题：[poj2774]求两个串的最长公共子串（l<100000）

　　解法：将两串相连，在中间加一个没用到的字符，求出height数组，在其中找一个最大的height，且所指的两个串一个在空字符前一个在空字符后。