后缀数组匹配字符串的问题
小弟在学习后缀数组匹配字符串的时候遇到一个问题，后缀数组的求法我会求了，这个地方没有疑问，我的疑问在利用后缀数组进行匹配的时候。例如源串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.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.str.length()>=p.length()&&(sa.str.substring(0, p.length()).compareTo(p)==0)) {
// if(sa.str.compareTo(p)>0) {
// return getRes(p, sa, start, mid-1);
// }
return sa.index;
}
if(p.compareTo(sa.str)<0) {//若p<sa.str会返回一个负数
return getRes(p, sa, start, mid-1);
}
else if(p.compareTo(sa.str)>0) {
return getRes(p, sa, mid+1, end);
}
else {
return sa.index;
}
}
private static Suff[] getSa(String s) {
// TODO Auto-generated method stub
Suff sa[]=new Suff;
for (int i = 0; i < s.length(); i++) {
String temp=s.substring(i);
sa=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;
}
}
}
当输入我这个的p和s时，控制台输出为4
页:
[1]