鱼C论坛

 找回密码
 立即注册
查看: 3872|回复: 1

后缀数组匹配字符串的问题

[复制链接]
发表于 2021-2-24 21:45:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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;
                }

        }

}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-2-24 21:46:32 | 显示全部楼层
当输入我这个的p和s时,控制台输出为4
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-22 13:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表