java – Knuth-Morris-Pratt算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – Knuth-Morris-Pratt算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1145字，纯文字阅读大概需要2分钟。

内容图文

是Knuth–Morris–Pratt algorithm的解决方案：干草堆：AAAAAAAAAA,针：AAA,这是：3,对吗？

因为,大海捞针有8个AAA实例,但据我所知,knuth-morris-pratt算法只能找到3.我想错了吗？

通过找出字符串中每个后缀的边框可以解决这个问题吗？

以下是我对KMP算法的实现：

public static int occurrenceOfSubstring(char[] target, char[] pattern) {
        int[] overlay = new int[pattern.length];
        overlay[0] = -1;
        overlay[1] = 0;

        int i = 0, j = 1;

        while (j + 1 < pattern.length) {
            if (pattern[i] == pattern[j]) {
                if (i == 0) {
                    overlay[j + 1] = 1;
                } else {
                    overlay[j + 1] = overlay[j] + 1;
                }
                i++;
                j++;
            } else if (pattern[j] == pattern[0]) {
                i = 0;
            } else {
                j++;
            }
        }

        int l = 0,count=0;

        for (int k = 0; k < target.length; k++) {
            if (target[k] == pattern[l]) {
                if (l == pattern.length - 1) {
                    l = 0;
                    count++;
                } else {
                    l++;
                }
            } else {
                l = overlay[l] == -1 ? 0 : overlay[l];
            }
        }
        return count;
    }

解决方法:

KMP专注于在完全匹配搜索失败时优化搜索,但可以重复使用部分匹配来重新开始搜索,而不是使用天真的方法.但是,您提供的案例没有部分匹配,它始终在每次搜索迭代时找到完整的单词.所以我确实希望KMP能够为你提出的案例返回3场比赛.请注意,这是一个边缘情况,可能会想要修改算法以利用干草堆或单词或两者的上下文信息,但您现在超越了KMP.希望这可以帮助.

内容总结

以上是互联网集市为您收集整理的java – Knuth-Morris-Pratt算法全部内容，希望文章能够帮你解决java – Knuth-Morris-Pratt算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---