KMP问题

1. KMP 解决的问题及其描述

字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。

如：

String str = "abc123def"; // 匹配串
String ptr = "123d"; // 模式串

返回起始位置 3

2. 很容易就能想到的暴力匹配解法

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

代码：

   public int getIndexOf(String str, String ptr){
        char[]   sArray  =  str.toCharArray();
        char[]   pArray  =  ptr.toCharArray();
    //    if(pArray.length > sArray.length) return -1;
        int  i = 0,j = 0;
        while (i< sArray.length && j < pArray.length){
            if( sArray[i] == pArray[j]){
                if(j == pArray.length-1){
                    return i-j;
                }
                i++;  j++;
            }else{
                //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
                i = i - j + 1;
                j = 0;
            }
        }
        return -1;
    }

3. 最长前缀和最长后缀匹配长度

要理解KMP问题，咱们先来理解下一个概念：最长前缀和最长后缀匹配的长度。

给定字符串 abcabcd ,求d前面子序列的最长前缀和最长后缀匹配的长度。

长	前缀	后缀	匹配结果
1	a	c	不匹配
2	ab	bc	不匹配
3	abc	abc	匹配
4	abca	cabc	不匹配
5	abcab	bcabc	不匹配
6	abcabc(不可取)	abcabc(不可取)	前缀不取尾，后缀不取头

d前面子序列的最长前缀和最长后缀匹配的匹配长度为3

初始匹配和 next数组 匹配失败时，模式串向右划过next[j]位,j位为不匹配的位置

使用next数组，匹配失败时,如果不存在重复的前缀或者后缀，即next数组的值是 -1,这时的处理逻辑与暴力解法一致。如果存在重复的前缀后缀，模式串大段地向后移，匹配串不需要回溯。时间复杂度为 O(n).

public int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int si = 0;
        int mi = 0;
        int[] next = getNextArray(ms);
        while (si < ss.length && mi < ms.length) {
            if (ss[si] == ms[mi]) {
                si++;
                mi++;
            } else if (next[mi] == -1) {
                si++;
            } else {
                mi = next[mi];
            }
        }
        return mi == ms.length ? si - mi : -1;
    }

    public int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length) {
            if (ms[pos - 1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }