引言：今天被这道题整笑了，也被这道题打醒了，原来我还没有真正的理解KMP算法
先来讲讲这道题有多有趣先：
一：
对于熟悉了解面向对象的封装性来说，解决这道题只需要一行代码哈哈哈有被笑到，以下是Java代码：
return haystack.indexOf(needle);
OK今天的面试到此结束，可以回去等通知了
二.
暴力枚举：每一个都进行比较
class Solution {
public int strStr(String haystack, String needle) {
if(needle.equals("")) return 0;
int slow, fast, m = haystack.length(), n = needle.length(), k;
for(slow = 0; slow < m - n + 1; slow++){
k = slow;
for(fast = 0; fast < n; fast++){
if(haystack.charAt(k) != needle.charAt(fast))
break;
k++;
}
if(fast == n) return slow;
}
return -1;
}
}
虽然都可以过，但性能太差，所以下面主角登场---------KMP算法，专治各种子串匹配：
说来惭愧，在使用它前我又忘了怎么算，于是又去翻了资料，于是出于胜负欲的刺激下，我这次要完完整整踏踏实实深深刻刻的干了KMP算法，并且做好笔记，理解每一处细节
下面先引入俩个概念：getNext数组要用到
前缀：包含第一个字符且不含最后一个字符
后缀：包含最后一个字符且不含第一个字符
注：前缀串与后缀串的对比都是从左到右！！
声明：下面可以跟着然后自己手算多练习几个，对理解后续的代码有很大帮助
1.首先，获取next[] 数组，下面我直接上图吧，扣字描述费键盘
需要的话就多手写几个例子，手写不难，主要是代码是理解较费劲
然后直接上代码：
public static void getNext(int[] next, String sonStr){
int len = sonStr.length();
char[] ch = sonStr.toCharArray();
int i = 0, k = 1;/*求从第三个起的前后缀相同字符个数，
//i表示前缀开始，k表示后缀开始（即每次的j-1）
因此第j个的表示是：k+1 */
next[0] = -1;
next[1] = 0;
while(k < len - 1 ){
if(i != -1 && ch[i] == ch[k]){
next[k+1] = i + 1;/*
这里就是第j个的赋值,
因为i从0开始，所以计算个数要+1
*/
i++;
k++;
}
else if(i == -1){
next[k + 1] = 0;
/*如果i == -1，就是说明第j个的前后缀没有相同的字符，就赋值0然后继续比较下一个，所以k++
那么前缀继续由第一个开始，即下标0，所以i++
*/
i++;
k++;
}
else{
//这里是重点，i = next[i]，我个人认为有动态规划的嫌疑
//因为此处前后缀不匹配，但也许前缀的i倒退几格就能与后缀匹配上了
//因此要借助前面的值才知道我们的i要推回哪里，回到-1就说明匹配不上，因此有动态规划的嫌疑
i = next[i];
}
}
}
下面开始分析：（代码有注释，可以看）
一：Next数组有俩个特数值：next[0] = -1, 与next[1] = 0,每一次求next[]可以直接先赋值，因为next[1]前只有一个字符，所以他即包含了第一个字符且含最后一个符，因此比不了（根据前缀和后缀的定义）。
所以也说明了子串要超过2个字符才能调用该方法，否则报错
二：
该方法求的是第 j 个，但要从第j -1个开始，而j -1又得看 j - 2的结果所以有动态规划的嫌疑，
详解可看上面代码的讲解
最后附上完整调试代码：
package FirstPackage;
public class KMP {
public static void main(String[] args) {
String fatherStr = "mississippi";
String sonStr = "issip";
System.out.println(testKMP(fatherStr,sonStr));
}
public static int testKMP(String fatherStr,String sonStr) {
int n = fatherStr.length(), m = sonStr.length();
if(m == 0) return 0;
else if(m < 2) {
return fatherStr.indexOf(sonStr.charAt(0));
}
else {
int[] next = new int[m];
getNext(next, sonStr);
int i = 0, j = 0;
//while循环一定要这么写，俩者一个不成立都不行，否则会报下标越界的错误
while( j < n && i < m ) {
if(i == -1 || fatherStr.charAt(j) == sonStr.charAt(i)) {
i++;
j++;
}
else i = next[i]; //不匹配 i 就回到i该回去的地方
}
if(i == m) return j - i; //举例手算一下，就是这个值
else return -1;
}
}
public static void getNext(int[] next, String sonStr){
int len = sonStr.length();
char[] ch = sonStr.toCharArray();
int i = 0, k = 1;
next[0] = -1;
next[1] = 0;
while(k < len - 1 ){
if(i != -1 && ch[i] == ch[k]){
next[k+1] = i + 1;
i++;
k++;
}
else if(i == -1){
next[k + 1] = 0;
i++;
k++;
}
else{
i = next[i];
}
}
}
}
然后我们再提交一下结果，看看KMP的性能：
测试代码如下：–这里所有可能情况都一一考虑到了
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if(m == 0) return 0;
else if(m < 2) {
return haystack.indexOf(needle.charAt(0));
}
else {
int[] next = new int[m];
getNext(next, needle);
int i = 0, j = 0;
while( j < n && i < m ) {
if(i == -1 || haystack.charAt(j) == needle.charAt(i)) {
i++;
j++;
}
else i = next[i];
}
if(i == m) return j - i;
else return -1;
}
}
public static void getNext(int[] next, String sonStr){
int len = sonStr.length();
char[] ch = sonStr.toCharArray();
int i = 0, k = 1;
next[0] = -1;
next[1] = 0;
while(k < len - 1 ){
if(i != -1 && ch[i] == ch[k]){
next[k+1] = i + 1;
i++;
k++;
}
else if(i == -1){
next[k + 1] = 0;
i++;
k++;
}
else{
i = next[i];
}
}
}
}
哇giao，大佬们研究的算法就是不一样。而对于我这种菜鸟，只需要站在巨人的肩膀上，记住和学习他们的思想就行了
好了，文章到这里终于结束，希望这次能真正地悟道巨人们的思想，资料不再翻来翻去