马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
小弟在学习后缀数组匹配字符串的时候遇到一个问题,后缀数组的求法我会求了,这个地方没有疑问,我的疑问在利用后缀数组进行匹配的时候。
例如源串s="babababab",待匹配串p="ba",我学习到的代码是利用二分查找来进行匹配,我的代码可以实现正确的查找功能,可是当p在s中有多个地方可以匹配的时候,它只能输出其中的一次,请问这就是利用后缀数组进行字符串匹配的缺陷吗?import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="babababab";
String p="ba";
Suff sa[]=getSa(s);
for (int i = 0; i < sa.length; i++) {
System.out.println(sa[i].toString());
}
int resIndex=getRes(p,sa,0,s.length()-1);
System.out.println(resIndex);
}
private static int getRes(String p, Suff[] sa, int start, int end) {
// TODO Auto-generated method stub
int mid=start+((end-start)>>1);
if(start>end) {
return -1;
}
if(sa[mid].str.length()>=p.length()&&(sa[mid].str.substring(0, p.length()).compareTo(p)==0)) {
// if(sa[mid].str.compareTo(p)>0) {
// return getRes(p, sa, start, mid-1);
// }
return sa[mid].index;
}
if(p.compareTo(sa[mid].str)<0) { //若p<sa[mid].str会返回一个负数
return getRes(p, sa, start, mid-1);
}
else if(p.compareTo(sa[mid].str)>0) {
return getRes(p, sa, mid+1, end);
}
else {
return sa[mid].index;
}
}
private static Suff[] getSa(String s) {
// TODO Auto-generated method stub
Suff sa[]=new Suff[s.length()];
for (int i = 0; i < s.length(); i++) {
String temp=s.substring(i);
sa[i]=new Suff(temp,i);
}
Arrays.sort(sa);
return sa;
}
//记得这里要加static
public static class Suff implements Comparable<Suff> { // 意思是必须自己重新实现Comparable的意思
String str;
int index;
public Suff(String str, int index) {
this.str = str;
this.index = index;
}
public int compareTo(Suff o2) {
return this.str.compareTo(o2.str);
}
public String toString() {
return "Suff:"+this.str+" "+"index:"+this.index;
}
}
}
|