轉貼至 http://gisyhy.blog.163.com/blog/static/1293903432010590730281/

1、概念

2、倍增算法

3、涉及的所有定理的证明。

4、对于height[]数组的求解和理解。

5、程序模板

一、概念：

1、字符集：简单的说就是字符的集合，但是有个条件，所有字符具有可比性，即有大小关系。

2、字符串：我们用S表示，起始下标为1，终止为n。

3、子串：S中连续的字符串，表示为S[i...j]，1<=i <=j <=n。

4、后缀：用suffix(i)表示S[i....n]子串。

5、后缀数组：sa[1-n]，sa[i]表示第i小的后缀为suffix(sa[i])。即suffix(sa[i])<=suffix(sa[i+1])。

6、名次数组：rank[1-n],rank[i]表示suffix(i)的名次，第rank[i]小。

备注：字符串的大小怎么定义的？

定义两个字符串s1[],s2[],那么我只说明if(len(s1) < len (s2))，那么s1串要小。

那么我们将S字符串的尾部加入一个'$'，他表示字符集中大小最小的字符。即S[n]='$'。

二、倍增算法（DA）：

定义：

uk ：表示字符串u的前k个字符组成的字符串。

k<=len(u)，那么uk= u[1...k]；

k>len(u)，那么uk= u。

就有性质：suffix(i)2k < suffix(j)2k ，那么<=> suffix(i)k < suffix(j)k  或者 (suffix(i)k= suffix(j)k  且 suffix(i+k)k < suffix(j+k)k)。

怎么求sa，rank？

定义：sa[]k,rank[]k。

sa[i]k：表示k前缀的后缀中第i小的字符串为suffix(sa[i]k)k。

rank[i]k：表示k前缀的后缀suffix(i)k的名次为rank[i]k。

如果求sa[]2k,rank[]2k，那么我们可以通过sa[]k,rank[]k得到，怎么得到的呢？

我们利用性质可以通过rank[]k得到sa[]2k：

if(suffix(sa[i]2k)2k < suffix(sa[j]2k)2k)  ，那么 <=>  rank[i]k < rank[k]  或者 （rank[i]k == rank[j]k  且

（i+k <=n ? rank[i+k]k:0）< （j+k <=n ? rank[j+k]k :0））。

我们看到要限制i+k <=n ,j+k <=n，这是因为如果超出了S串那么肯定为最小字符串，这里用0表示最小就可以。

我们可以用sort排序就可以得到，但是还可以用基数排序为o(n)，但是我觉得一般情况下没必要。

三、定理证明：

这里我们要有些定义：

lcp(suffix(i),suffix(j))：表示它们的最长公共前缀。

LCP(i,j)：表示LCP(i,j)= lcp(suffix(sa[i]), suffix(sa[j]))。

height[i]：表示height[i]=LCP(i-1,i)，height[1]=0;

h[i]：表示h[i]=height[rank[i]]。

定理概括：

1、LCP(i,j) = LCP(j,i)。

2、LCP(i,i) = len(suffix(i))。

3、LCP(i,j) = min{LCP(k-1,k)} , i+1 <=k <=j。

4、对于 1<=i< j<k<=n，LCP(i,k) = min{LCP(i,j),LCP(j,k)}。

5、对于 1<=i<=j<k<=n，LCP(j,k) >= LCP(i,k)。

6、对于i >1 , rank[i] >1 , 那么 h[i] >=h[i-1] -1。

定理1、2是显然成立的，就不证明了。

定理4证明：

对于 1<=i<j <k <=n，那么LCP(i,k) =min{LCP(i,j),LCP(j,k)}。

我们令p = min{LCP(i,j),LCP(j,k)}.         (1)

如果我们证明LCP(i,k) >=p 且 LCP(i,k)<=p ,就ok了。

令suffix(sa[i]) =u,suffix(sa[j]) =v, suffix(sa[k]) =w;

那么由(1)可以知道：up=vp, vp=wp。所以up= wp => LCP(i,k) >=p。 （2）

我们令LCP（i,k）= q > p。

那么可以推出：up =vp =wp 。                    （3）

由(1)我们还可以知道：u[p+1]!=v[p+1] 或者 v[p+1]!=w[p+1]，（4）

分析：如果u[p+1]=v[p+1] 且 v[p+1]=w[p+1] ，那么min{LCP(i,j),LCP(j,k)} =p+1>p与(1)矛盾。

我们令u[p+1]=x,v[p+1]=y,w[p+1]=z 。

由 1<=i <j<k<=n，up = vp=wp ，我们知道 x <=y<=z      （5）

又有q>p => q>=p+1, =>  x= z 。 联合（5）可以知道：x=y=z   （6）

好了很明显(4)和（6）矛盾了。因此我们知道  LCP(i,k)  =q <=p。（7）

通过（2）和（7）得到了结论：LCP（i,k）=p = LCP(i,j),LCP(j,k)}。

定理3证明：

其实通过定理4可以顺利证明定理3。

LCP(i,j) = min{LCP(k-1,k)} , i+1 <=k <=j。

 令1<=i<k<j<=n。

min{LCP(i,i+1), ...,  LCP(k-1,k),LCP(k,k+1),..., LCP(j-1,j)} = min{min{LCP(i,i+1),...,LCP(k-1,k)},min{LCP(k,k+1),...,LCP(j-1,j)}}

= min{LCP(i,k),LCP(k,j)} = LCP(i,j)。[定理3]

定理5证明：

对于 1<=i<=j<k<=n，LCP(j,k) >= LCP(i,k)。

如果1<=i=j<k<=n。LCP(j,k)= LCP(i,k).

如果1<=i<j<k<=n，那么LCP(i,k) =min{LCP(i,j),LCP(j,k)}. =>  LCP(j,k) >=LCP(i,k)。

定理6的证明：

对于i >1 , rank[i] >1 , 那么 h[i] >=h[i-1] -1。

如果h[i-1]<=1 ，h[i]>=0 >= h[i-1]-1。

如果h[i-1]>1,令j= i-1, k = sa[rank[j]-1]。

显然 suffix(k) < suffix(j)。（因为rank[k]=rank[j]-1 < rank[j]）。（1）

h[i-1]= height[rank[i-1]]=LCP(rank[i-1]-1,rank[i-1]) = LCP(rank[j]-1,rank[j])=lcp(suffix(k),suffix(j)) > 1。(2)

由（2）可以知道：lcp(suffix(k+1),suffix(j+1))=lcp(suffix(k+1),suffix(i)) =h[i-1]-1。

分析：因为lcp(suffix(k),suffix(j)) > 1，因此我们知道s[k]=s[j]，因此lcp(suffix(k+1),suffix(j+1)) =lcp(suffix(k),suffix(j)) -1。

由（1）、（2）可以得到rank[k+1]  < rank[j+1]=rank[i]  => rank[k+1] <= rank[i]-1。

因为1<=rank[k+1] <=rank[i]-1 < rank[i]，通过定理5可以知道：

LCP(rank[i]-1,rank[i]) >= LCP(rank[k+1],rank[i]) = lcp(suffix(k+1),suffix(i)) = h[i-1]-1。

h[i]=height[rank[i]]= LCP(rank[i]-1,rank[i]) >= h[i-1]-1。的证。

好了，运用定理6，我们可以得到非常想要的结果。

四、height[]数组的求解过程和理解：

其实定理6是为求解height数组做准备，以便优化时间而得到的定理。

有了定理6，我们可以在线性时间（具体复杂度求解就不说了）内得到height数组。

通过分析，我们发现，rank[i]=1,的情况下其实就i=n，因为最后末尾的'$'字符串肯定为最小后缀。

如果i=1, 则说明是起始位置，因为我们suffix(sa[rank[i]-1])和suffix(sa[rank[i]])的0位置开始比较，得到最大公共前缀个数。

如果h[i-1] <=1，那么h[i-1]-1 <=0，对于当前开始比较位置依旧为0，因为最小肯定从开头开始比较啦。

如果rank[i] >1 且 i >1 ，且h[i-1] >1，那么就可以从h[i-1]开始比较，我们知道h[i-1]是最大公共前缀个数,我们知道对于h[i]>=h[i-1]-1，那么也就是 说对于suffix(sa[rank[i]-1])和suffix(sa[rank[i]]),肯定有h[i-1]-1个字符已经匹配了，那么我们从下一 个字符开始匹配就可以了。

求出h数组在用o(n)时间将height数组求出，h[i]=height[rank[i]]。

五、程序模板：

求sa[],rank[],height[]的程序模板：

const int N =20002;

int n,s[N];//原始字符串
int sa[N],rank[N],K,height[N],rk[N],h[N];
bool cmp1(const int & a,const int & b)
{
 return s[a] < s[b];
}
bool cmp2(const int & a,const int & b)
{
 return ((rank[a] < rank[b]) || (rank[a]==rank[b] && 
  ((a+K<=n ? rank[a+K]:0) <(b+K <=n ? rank[b+K]:0))));
}
void suffix_array()
{
 int i;
 for(i=1;i<=n;i++)
  sa[i]=i;
 sort(sa+1,sa+n+1,cmp1);//初始sa[]1
 for(i=1;i<=n;i++){//初始化rank[]1
  if(i==1 || s[sa[i]]!=s[sa[i-1]])
   rank[sa[i]]=i;
  else rank[sa[i]]=rank[sa[i-1]];
 }
 for(K=1; K<n; K*=2){
  sort(sa+1,sa+n+1,cmp2);//求出sa[]2K
  for(i=1;i<=n;i++){
   if(i==1 || cmp2(sa[i],sa[i-1]) || cmp2(sa[i-1],sa[i]))
    rk[sa[i]]=i;
   else rk[sa[i]]= rk[sa[i-1]];
  }
  memcpy(rank,rk,(n+1)*sizeof(int));//求出rank[]2K
 }

 int k;
 for(i=1;i<=n;i++)//求h[]
 {
  if(rank[i]==1){h[i]=0;continue;}
  if(i==1 || h[i-1]<=1)k=0;
  else k = h[i-1]-1;
  while(s[sa[rank[i]-1]+k]==s[sa[rank[i]]+k])k++;
  h[i]=k;
 }
 for(i=1;i<=n;i++)height[rank[i]]=h[i];//求height[]
 }

我们可以在求h的时候就用height代替，h[i]=height[rank[i]]，就可以节约o(n)的空间复杂度。

就可以把求height简化一下：

int k;
 for(i=1;i<=n;i++)
 {
  if(rank[i]==1){height[1]=0;continue;}
  if(i==1 || height[rank[i-1]]<=1)k=0;
  else k = height[rank[i-1]]-1;
  while(s[sa[rank[i]-1]+k]==s[sa[rank[i]]+k])k++;
  height[rank[i]]=k;
 }