本文主要是介绍KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、KMP算法（-1版本）：

class Solution {

    public int strStr(String haystack, String needle) {        
        if(needle.length()==0) return 0;

        int M = haystack.length();
        int m = needle.length();

        char[] S = haystack.toCharArray();
        char[] s = needle.toCharArray();

        int[] next = new int[m];
        next[0] = -1;
        for (int i = 1,j = -1; i<m; i++){
            while(j>=0 && s[i] != s[j+1])  j = next[j];
            if(s[i] == s[j+1])  j++;
            next[i] = j;
        }

        
        for(int i = 0,j = -1; i<M; i++){
            while(j>=0 && S[i] != s[j+1])  j = next[j];
            if(S[i]==s[j+1])  j++;
            if(j+1==m)  return (i-m+1);
        }

        return -1;
    }

}

二、KMP算法原理：

【宫水三叶】简单题学 KMP 算法

三、Next数组的原理：

「代码随想录」KMP算法详解

1.字符串的下标是从0开始的

2.比较的指针是j+1,而不是j

3.next[ j ]存放的是：前 j 个字符（包括j）的最大相同前后缀的长度-1

4. j = next[ j ] 的含义：（详细讲解在下面原理链接）

四、next数组中 j = next[ j ]的原理：

KMP算法之求next数组代码讲解

1.字符串的下标是从1开始的

2.比较的指针就是j

3.next[ j ]存放的是：前j-1个字符的最大相同前后缀的长度+1（这样j跳转的时候指的是前缀后一个位置）

4.while的判断条件是错误的，当i=length时  还++i，会导致数组越界；改为 1<length。

这篇关于KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！