字符串匹配的后缀数组
概念：后缀数组：这是对所有后缀进行字典排序后记录在数组中的第一个后缀。 sa[0]=5、开始下标为5后缀
在所有后缀中词典最小。
rank数组：是给定后缀的下标，返回词典顺序。 rank[5]=0 rank[sa[i]]=i
后缀数组主要是为了匹配。 子字符串：必须是后缀的前缀字符串
求height数组。 height数组是两个后缀的公共前缀的长度
可以使用暴利求法，但复杂度高，也可以使用其他方法
根据rank排名和hg[rank[i]]hg[rank[i-1]] 1，推论数学式。
为了让后面一直在k上可以看到，下次直接跳过k个字符进行比较
k 1个，如果不相同则直接返回k，如果相同则k
1、首先求出原来的rank数组
2 )基于I字符串排名获得rk值，rk-1获得前一排名值。 根据sa序列和rk关系求出
的原始字符串的位置j .然后比较i k，j k的字符是否相同。
代码如下所示
公共int [ ] getheight (string src，Suff[] sa ) )。
{
int src_length=src.length (；
int [] rk=new int[src_length]；
//rank表示为了避免重复的排行榜0-n-1
for(intI=0； isrc_length； I )
rk[sa[i].index]=i；
int [] hg=new int [src_length]；
int k=0；
for(intI=0； isrc_length； I )
int rk_i=rk[i]；
if(rk_I==0) {
hg[0]=0；
contine
}
int rk_i-1=rk_i -1；
int j=sa[rankpre].index；
是if(k0 )
k----；
for (； j klengthi klength； k )
{
if(src.Charat(JK )！=src.Charat(Ik ) )
黑；
}
hg[rk_i]=k；
}
return hg；