后缀数组之倍增法

还没搞懂，汗。。先保存下资料以后有时间再仔细研究吧。
后缀数组资料1：http://www.cppblog.com/superKiki/archive/2010/05/15/115421.html
资料2：http://blog.sina.com.cn/s/blog_69fd58a10100za77.html
后缀数组就是将字符串所有后缀排序后的数组，设字符串为S，令后缀Suffix(i)表示S[i..len(S)]。用两个数组记录所有后缀的排序结果：

Rank[i]记录Suffix(i)排序后的序号，即Suffix[i]在所有后缀中是第Rank[i]小的后缀

SA[i]记录第i位后缀的首字母位置，即Suffix[SA[i]]在所有后缀中是第i小的后缀

然后就是怎么快速求所有后缀的顺序了，其中的关键是如何减少两个后缀比较的复杂度
方法是倍增法，定义一个字符串的k-前缀为该字符串的前k个字符组成的串，关于在k-后缀上的定义Suffix(k,i)、SA[k,i]和Rank[k,i]类似于前，则有

若Rank[k,i]＝Rank[k,j]且Rank[k,i+k]＝Rank[k,j+k]，则Suffix[2k,i]＝Suffix[2k,j]
若Rank[k,i]＝Rank[k,j]且Rank[k,i+k]<Rank[k,j+k]，则Suffix[2k,i]<Suffix[2k,j]
若Rank[k,i]<Rank[k,j]，则Suffix[2k,i]<Suffix[2k,j]

这样就能在常数时间内比较Suffix(2^k, i)之间的大小，从而对Suffix(2^k,i)进行排序，最后当2^k>n时，Suffix(2^k, i)之间的大小即为所有后缀之间的大小

于是求出了所有后缀的排序，有什么用呢？主要是用于求它们之间的最长公共前缀（Longest Common Prefix，LCP）

令LCP(i,j)为第i小的后缀和第j小的后缀（也就是Suffix(SA[i])和Suffix(SA[j])）的最长公共前缀的长度，则有如下两个性质：

对任意i<=k<=j，有LCP(i,j) = min(LCP(i,k),LCP(k,j))
LCP(i,j)=min(i<k<=j)(LCP(k-1,k))

第一个性质是显然的，它的意义在于可以用来证明第二个性质。第二个性质的意义在于提供了一个将LCP问题转换为RMQ问题的方法：
令height[i]＝LCP(i-1,i)，即height[i]代表第i小的后缀与第i-1小的后缀的LCP，则求LCP(i,j)就等于求height[i+1]~height[j]之间的RMQ，套用RMQ算法就可以了，复杂度是预处理O(nlogn)，查询O(1)

然后height的求法要用到另一个数组：令h[i]=height[Rank[i]]，即h[i]表示Suffix(i)的height值（同时height[i]就表示Suffix(SA[i])的height值），则有height[i]=h[SA[i]]
然后h[i]有个性质：

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

用这个性质我们在计算h[i]的时候进行后缀比较时只需从第h[i-1]位起比较，从而总的比较的复杂度是O(n)，也就是说h数组在O(n)的时间内解决了。求出了h数组，根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组，于是可以在O(n)时间内求出height数组，从而整个LCP问题就解决了。

然后后缀数组的应用就是利用它的LCP在需要字符串比较时降低复杂度。同时由于后缀数组的有序性可以很方便地使用二分

于是总结一下要点：

利用倍增算法在O(nlogn)的时间内对后缀数组进行排序
利用h数组的性质在O(n)的时间内求出储存排序后相邻后缀间的LCP数的组height
利用LCP的性质将平凡LCP问题转化为height数组上的RMQ问题

HDOJ1403：http://acm.hdu.edu.cn/showproblem.php?pid=1403
分析：http://www.cnblogs.com/zhuangli/archive/2008/08/18/1270608.html

#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;
const int maxn=200005;
int wa[maxn],wb[maxn],wv[maxn],wt[maxn],r[maxn],sa[maxn];
char str[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++)wt[i]=0;
    for(i=0;i<n;i++)wt[x[i]=r[i]]++;
    for(i=1;i<m;i++)wt[i]+=wt[i-1];
    for(i=n-1;i>=0;i--)sa[--wt[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p)
    {
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)wv[i]=x[y[i]];
        for(i=0;i<m;i++)wt[i]=0;
        for(i=0;i<n;i++)wt[wv[i]]++;
        for(i=1;i<m;i++)wt[i]+=wt[i-1];
        for(i=n-1;i>=0;i--)sa[--wt[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1;i<=n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
    return;
}
int main(int argc, char** argv) {
    while(cin>>str)
    {
        int pos=strlen(str);
        str[pos]='$';
        cin>>str+pos+1;
        int n=strlen(str);
        for(int i=0;i<n;i++)r[i]=(int)str[i];
        r[n]=0;
        da(r,sa,n+1,130);;
        calheight(r,sa,n);
        int maxl=0;
        for(int i=2;i<=n;i++)
        {
            int a=sa[i-1],b=sa[i];
            if((a<pos&&b>pos)||(a>pos&&b<pos))
            if(height[i]>maxl)maxl=height[i];
        }
        printf("%d\n",maxl);

    }
    return (EXIT_SUCCESS);
}

PKU2774(完全可以用HDOJ1403代码AC)：http://poj.org/problem?id=2774

本题是求两字符串的最长公共子串（注意是子串不是子序列），构造出SA,RA和HEIGHT后，答案就是最大的HEIGHT，但这个最大的HEIGHT可能是同一个串中的，所以这个最大的HEIGHT同时要满足sa[i-1]和sa[i]不在同一个串中。

分析：http://www.cnblogs.com/zgmf_x20a/archive/2008/11/21/1338539.html