KMP算法 Java实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了KMP算法 Java实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem: 28. 找出字符串中第一个匹配项的下标

解题方法
思路
- 构建next数组
- 回溯查找
复杂度
Code

解题方法

构建next串
回溯查找next串,最后下标

思路

通过最大前缀后缀能找到下一次未查找到后要回溯的位置

构建next数组

无论如何第一个数的下一次回溯位置肯定是0,因此next[0]=0
这里的 j表示前缀起始位置 i表示后缀起始位置
如果找到字符不相同到的话,就让他一直回溯找,并且回溯赋值j = next[j-1]
能找到相同字符的话就直接i++,j++,并且把next[i] = j
这里先写while判断不相同后写相同,是因为不相同的终点
一定是有相同的后缀或者直接结束查找(到了字符串末尾)

回溯查找

其实和上面的思路差不多,不能查找相同字符就一直回溯,能的话就共同前进,直到j到了模式串长度
这时因为i也在前进,所以i的下标是 应该返回的下标+(匹配串的长-1)

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(m+n)$

空间复杂度:

添加空间复杂度, 示例： $O(m)$文章来源地址https://www.toymoban.com/news/detail-854483.html

Code

class Solution {

    public int strStr(String haystack, String needle) {
        return new KMP(needle).search(haystack);
    }

    public class KMP {
        private String pattern;   // 模式串
        private int[] next;
        public KMP(String pattern){
            this.pattern = pattern;
            int m = pattern.length();
            // 创建next 数组
            next = new int[m];
            next[0] = 0;
            for(int i = 1,j=0; i < m; i++){
                while(j>0&&pattern.charAt(i)!=pattern.charAt(j)){
                    j = next[j-1];
                }
                if(pattern.charAt(i) == pattern.charAt(j)){
                    j++;
                }
                next[i] = j;
            }
        }

        public int search(String text){
            int j = 0;
            for(int i=0;i<text.length();i++){
                while(j>0&&text.charAt(i) != pattern.charAt(j)){
                    j = next[j-1];
                }
                if(text.charAt(i) == pattern.charAt(j)){
                    j++;
                }
                if(j == pattern.length()){
                    return i-pattern.length()+1;
                }
            }
            return -1;
        }
    }

}

到了这里，关于KMP算法 Java实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！