KMP算法

一、使用场景

用于字符串匹配：

文本串：aabaabaaf

模式串：aabaaf

问：文本串是否包含模式串？如果包含，返回第一次出现的索引。

二、经典暴力匹配

遍历文本串，将得到的每一个字符作为首字母与模式串进行比较。

需要遍历一次文本串和一次模式串。(m为模式串长度，n为文本串长度)

时间复杂度O(m*n)

三、KMP算法思路

1、思路：

1. 遍历文本串（实际上并不是每一个字符都被遍历到）
2. 将文本串遍历的到的字符作为首字符和模式串进行比较。
3. 当比较到某个字符不相同时（如图的b，f），求出模式串中这个字符之前的所有字符的最长公共（相等）前后缀,如下图的aa
4. 接下在在从文本串中不相同的地方（b）和模式串中首部的最长公共前后缀（aa）的后一个字符（b）开始比较（如图蓝线）(实现方法见本文前缀表的使用)
5. 以此类推，如果比较相同，则匹配成功；如果不相同，则重复第3、4步。

2、KMP算法优点：

减少了比较最长公共前后缀（aa下图中2个紫色方框中的比较）的时间

原理：因为文本串中的aa已经和模式串中不相等字符的前面字符串的后缀比较过，并相等，而我们知道这部分的前后缀是相等的。不说了，看图（捂脸）。

3、前缀表的使用

前缀：不包含字符串最后一个字符

后缀：不包含字符串第一个字符

前缀表：

模式串	最长公共前后缀
a	0
aa	1
aab	0
aaba	1
aabaa	2
aabaaf	0

第一次比较在f出不相等，所以取f之前的字符串得到最长公共前后缀2,即为下一个应比较的模式串字符的索引（b）

四、代码实现

/**
     * 
     * @param str1 文本串
     * @param str2 模式串（子串）
     * @param next 前缀表（部分匹配表）, 是子串对应的最大公共前后缀
     * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
*/
public static int kmpSearch(String str1, String str2,) {

    int[] next = kmpNext(str2);
    //对文本串遍历 
    for(int i = 0, j = 0; i < str1.length(); i++) {

        //KMP算法核心点, 可以验证...
        //当遇到文本串和模式串不相等时
        while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
            //将j置为不相等的字符的前面所有字符串的最大公共前后缀
            j = next[j-1]; 
        }

        //如果相等，将模式串的指针右移
        if(str1.charAt(i) == str2.charAt(j)) {
            j++;
        }    

        //遍历到模式串的最后
        if(j == str2.length()) {//找到了 // j = 3 i 
            return i - j + 1;
        }
    }
    return  -1;
}

//获取到一个字符串(子串) 的前缀表（部分匹配表）
public static  int[] kmpNext(String dest) {
    //创建一个next 数组保存最大公共前后缀长度
    int[] next = new int[dest.length()];
    next[0] = 0; //如果字符串是长度为1 最大公共前后缀长度就是0

    //i为遍历模式串的索引，j为模式串索引i及之前全部字符串的最大公共前后缀
    //j还可以表示为模式串的前缀的索引（重点）
    for(int i = 1, j = 0; i < dest.length(); i++) {
        //当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
        //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
        //这时kmp算法的核心点
        //这里的解析看下图
        while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
            j = next[j-1];
        }

        //当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
        //也就是搜索到与前缀相等的地方
        if(dest.charAt(i) == dest.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

上面的红指针代表i

下面的红指针代表j

当遇到两红指针处数据不相等时，下面的红指针（j）就会发生蓝色箭头的跳转

1. 先获取不相等数据的前面的字符串的最大公共前后缀
2. 以该最大公共前后缀为字符索引找到对应的位置索引2的a
3. 再将这个字符与索引i的字符进行比较

目的：在不用再次比较索引7、8的值的情况下，准确的获得i处的公共前后缀。

五、总结

KMP太难了，所以我选择

public boolean contains(CharSequence s)
当且仅当此字符串包含指定的char值(也可传入String)序列时才返回true。

public int indexOf(String str)
返回指定字符第一次出现的字符串内的索引。

String s1 = "aabaabaaf";
String s2 = "aabaaf";

int i = s1.indexOf(s2);            //i=3，一行解决
boolean b = s1.contains(s2);    //true