公共静态suff [ ] getsa (strings )
{
suff [ ] suff arrays=news uff [ s.length ()；
//sa[i]=k所示的排在I的后缀从k开始
for(intI=0； is.length (； I )
{
suff arrays [ I ]=news uff (s.substring (I )，I )； //substring(I )表示从开始位置到结束位置
}
Arrays.sort(suffArrays )； //按词典顺序对数组进行排序
return SuffArrays；
}
//用二分法比对Suff序列中的一致序列
公共静态语音匹配()//
{
String s='AABABABABB '；
String p='BABB '；
//suff[]sa=Getsa(s；
suff[]sa=getsa2(s；
int l=0；
int r=s.length ()-1；
wile(r=L ) )。
{
intmid=L(r-L ) 1；
Suff midsuff=sa[mid]；
String suffStr=midsuff.str； //中间字符串
//(防止遗漏的) int compares后缀列和模式列的比较结果，分为长度大还是小等
int compares；
suff str.length (=p.length ) )
{
compares=suffstr.substring(0，p.length ) ).comPareto(p )；
}
else
{
compares=suffstr.comPareto(p；
}
if(compares0)
{
r=mid-1；
}
else if(compares0)
{
l=mid 1；
}
else
{
system.out.print(midsuff.index )；
黑；
}
}
}
//*
*思路： 1、构建suffaryy序列，使用rank[i]=k的信息进行比较
*不是字符串的比较。
*1个字符时，直接排序
*出现2、4、8的情况。 等待倍增的文字时，
*首先判断rank[i]和rank[j]是否相同，
*如果不同，请直接返回rank[i]-rank[j]比较规则。
*如果相同，则比较rank[i k/2]-rank[j k/2]
*由于外侧为logn圈，内侧为nlgn排序，所以整体的排序为nlg的平方。
*k=1，一个字，得到了sa，rk。
*k=2，利用前一个回合的rk快速比较两个后缀
* k=4 .
*/
公共静态子系统[ ] gets a2 (stringsc ) )。
{
int length = sc.length();
final int rk[] = new int[length];
Suff[] suffA = new Suff[length];
for(int k =1;k<=length;k=k*2)//k也可以等于length，k代表截取范围，刚开始截取一个字符，而后是两个字符，，，，
{
for(int i=0;i<length;i++)
{
String suff = sc.substring(i, i+k>length?length:i+k);
suffA[i] = new Suff(suff,i);
}
if(k==1)//一个字符，直接进行排序
{
Arrays.sort(suffA);//nlogn
}
else
{ final int kk=k;
Arrays.sort(suffA, new Comparator<Suff>(){
//不是基于字符串比较，而是用之前的rank
@Override
public int compare(Suff o1, Suff o2)
{
int i=o1.index;
int j=o2.index;
if(rk[i]==rk[j])
{
try
{
return rk[i+kk/2] - rk[j+kk/2];//用个好的变量kk
}catch (ArrayIndexOutOfBoundsException e) //数组越界异常对象为e
{
return o1.str.length()-o2.str.length();
}
}
else //如果第一个不等直接返回差值
{
return rk[i]-rk[j];
}
}
});
}
//排序完成后产生rank，给定下标，产生排名
int r=0;
rk[suffA[0].index] =r;
for (int i=0;i<length;i++)
{
if(suffA[i].compareTo(suffA[i-1])==0)
{
rk[suffA[i].index]=r;
}
else
{
rk[suffA[i].index]=++r;
}
}
}
return suffA;
}
**
*
* 后缀数组的实现类
*思路1，构造后缀数组，按照字符串的从小到大的字典顺序排列，数组的内容按照字符串+原始序列排序
*/
class Suff implements Comparable<Suff>{
String str;//后缀字符串内容
int index;//后缀的起始下标
public Suff(String str, int index)
{
this.str = str;
this.index = index;
}
@Override
public int compareTo(Suff o2) {
return this.str.compareTo(o2.str);
}
@Override
public String toString()
{
return "Suff{"+
"str="+str+'''+
", index"+index+
'}';
}
}