栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java

 public static void main(String[] args) {
        String model = "aababcabcacbab";
        String needle = "abcac";
        int index = str(model, needle);
        System.out.println(index);
    }

    public static int str(String model, String needle) {

        int[] next = new int[needle.length()];
        if (needle.length() == 0) {
            return 0;
        }
//        先计算出next函数对应值
        for (int left = 0, right = 1; right < needle.length(); right++) {
//            不相等时left指针回退
            while (left > 0 && needle.charAt(left) != needle.charAt(right)) {
                left = next[left - 1];
            }
            if (needle.charAt(left) == needle.charAt(right)) {
                left++;
            }
            next[right] = left;
        }
//        next数组装填完毕,进行字符串比对
        for (int i = 0, j = 0; i < model.length(); i++) {
            while (j > 0 && model.charAt(i) != needle.charAt(j)) {
//                当检测到不行等的字符时,就将模式串指针回退一个查找前一个的next[]对应的值,
//                数组中的值的含义是:在模式串中存在的最长匹配前缀和匹配后缀的长度是多少
//                因为在出现模式串和珠串字符不匹配时,可以确定模式串中,从不匹配的字符开始(但不包含),以前的串已经匹配完毕
//                最长匹配后缀与主串中对应字符串相等,也就表示最长匹配前缀与主串中的对应字符串相等,不用与主串再次匹配
//                如果回退过程中,在没有回退到原点时就可以匹配上那么就从此处开始继续匹配
                j = next[j - 1];
            }
            if (model.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
//                返回字符串配配完成时对应的主串位置
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

学习连接:leetCode字符串匹配KMP算法详解

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/964037.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号