Java教程

KMP算法

本文主要是介绍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算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!