KMP算法

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

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前以及匹配的文本内容，可以利用这些信息避免从头再去做匹配。如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

这个next数组为前缀表，代表的是模式串中当前位置及其之前的子串相同前后缀的长度的最大值。（这里需要说明的是前缀和后缀的定义：字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续字串，后缀不包含第一个字符的所有以最后一个字符结尾的连续字串）。

在字符串匹配的时候，在一个位置匹配不成功，则这个位置可以看作后缀子串的后一个位置，我们下一步是找到前缀子串的后一个位置，与之前匹配不成功的文本串同一个位置接着匹配。

KMP算法最难的部分当属next数组的生成，在实际的代码中有两种KMP算法，一个是原始的，另一个是将原始next整体右移一位，第一位为-1，或者看作所有位-1。这里使用的是原始的。生成next数组只需要模式串，i为后缀子串的末尾下标，j为前缀子串的末尾下标。如果这两位置的字符相同，j++,这是j的值就代表相同前后缀的长度，不同就要寻找之前的长度，比较那是的j与现在的i是不是相同，一直到找到或者到边界。

class Solution {
    //前缀表（不减一）Java实现
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) 
                j++;
            next[i] = j; 
        }
    }
}

// next数组减一
class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i<s.length(); i++){
            while(j>=0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }

            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i<haystack.length();i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
}

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