public static Suff[] getSa(String s)
{
Suff [] SuffArrays = new Suff[s.length()];
//sa[i]=k表明的排名为i的后缀是从k开始的
for(int i=0;i<s.length();i++)
{
SuffArrays[i]=new Suff(s.substring(i),i);//substring（i）代表从起始位置到结束
}
Arrays.sort(SuffArrays);//对数组按照字典顺序排序
return SuffArrays;
}
//用二分法去匹配Suff数组中的匹配数组
public static void match() //
{
String s ="AABABABABB";
String p = "BABB";
//Suff [] sa = getSa(s);
Suff [] sa = getSa2(s);
int l = 0;
int r =s.length()-1;
while(r>=l)
{
int mid = l+((r-l)>>1);
Suff midsuff = sa[mid];
String suffStr = midsuff.str;//中间字符串
///(防止遗漏)int compares 后缀串和模式串比较结果，分为长度是否大于或者长度小于等
int compares;
if(suffStr.length()>=p.length())
{
compares = suffStr.substring(0, p.length()).compareTo(p);
}
else
{
compares = suffStr.compareTo(p);
}
if(compares>0)
{
r=mid-1;
}
else if(compares<0)
{
l = mid+1;
}
else
{
System.out.print(midsuff.index);
break;
}
}
}
/**
* 思路：1，构造suffaryy数组，利用rank[i]=k的信息进行比较
* 而不是字符串的比较进行。
* 如果出现是一个字符的话，直接排序
* 如果出现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...
*/
public static Suff [] getSa2(String sc)
{
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+
'}';
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
