字符串匹配(KMP)

字符串匹配问题，求匹配串中模式串的位置. 

【1】暴力搜索, 每次匹配的过程假如匹配失败则 重新从模式串的开头位置和被匹配串的下一个位置开始匹配, 因为每个过程都是独立的，所以效率不高.

【2】KMP算法, 问题是由模式串引起的,因为从被匹配串找到模式串,    一次字符比对过程可以帮助下一次匹配.

2.1 最长的 前缀和后缀

假如有 abcabcd 字符串, d字符前面有"abcabc"字符串, 这个字符串 最长的相等前缀和后缀是"abc", "abc". 所以如果d这个位置字符想要保存信息, 应该保存这种前缀后缀长度匹配的信息, 3;

2.2 next数组

所以需要一个数组存储模式串的信息, 比如有

aaaab这个模式串, next[0] = -1,因为0位置之前没有字符,所以认为规定-1;   next[1] 它的前后缀不存在,所以next[1]=0;

next[2] 前面有aa字符串, 前缀为"a"后最为"a"时匹配，所以next[2] = 1......

2.3 匹配流程(重点)

假设str1 是被匹配串, str2是模式串; str1与str2匹配到分别是x和y位置时不等, 这时str2并不是用它的0号元素和str1的i+1号元素匹配，因为可以证明 (i, j)位置不可能匹配出str2串: 我们假设(i, j)中间存在一个k( i < k < j) 位置，从它开始到x-1位置至少和str2的[0, ?)相等， 但是事实上并不存在，如果存在的话就和最长相等前后缀相矛盾了, 如图 前后缀是str2第一个圈和str1某个位置匹配的话，一定是j位置...

其实这就避免了(i,j)的不必要的匹配, 这就是核心想法.

2.4 求next数组 (重点)

public int[] getNext(char[] model) {
        if (model.length == 1) {
            return new int[] {-1};
        }
        int[] next = new int[model.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int td;
        while (i < model.length) {
            /*
             * 我们要求出Next[i]的值
             * 前提,我们已经知道了next[i-1]的值.
             * 
             * [ i-1 前缀] k [ i-1 的后缀] [i-1] [i]
             * 1. 如果model[i-1] 的值 = model[k], next[i] = next[i-1]+1
             * 2. 不等时->  [k的前缀] k2 [k的后缀] k = [ i-1 的后缀 ] 
             *             退而求其次: 我们再比较model[i-1]和 model[k2], 一直到数组0下标
             */
            td = next[i-1];
            if (model[i-1] == model[td]) {
                next[i ++] = td + 1;
            } else if (td > 0) {
                td = next[td];
            } else {
                next[i ++] = 0;
            }
        }
        return next;
    }

kmp算法代码

public int kmp(String str, String model) {
        if (model.length() > str.length()) {
            return -1;
        } else if (model.length() == str.length()) {
            return model.equals(str)? 0:-1; 
        }
        
        int[] next = getNext(model.toCharArray());
        
        int i = 0; int j = 0;
        while (i < str.length() && j < model.length()) {
            if (model.charAt(j) != str.charAt(i)) {
                j = next[j];
                if (j == -1) {
                    i++;
                    j = 0;
                }
            } else {
                j++;
                i++;
            }
        }
        if (j == model.length()) {
            return i - j;
        }
        return -1;
    }