KMP算法假定了解案件的原则，其实很easy。

KMP算法简述

关于根据自己的理解在这里。

KMP三位发明者（Knuth、Morris、Pratt）的首字母组成，又称字符串查找算法。

个人认为能够理解为最小回溯算法，即匹配失效的时候，尽量少回溯。从而缩短时间复杂度。

KMP算法有两个关键的地方，1）求解next数组。2）利用next数组进行最小回溯。

1）求解next数组

next数组的取值仅仅与模式串有关，next数组用于失配时回溯使用。

在简单版本号的KMP算法中。每一个位置 j 的 next 值表示的是模式串的最长前缀的最后一个字符的位置（如果为 k ），当中最长前缀（长度为 k+1 ）须要与模式串截至当前位置长度亦为 k+1 的后缀匹配，且 k 最大为 j-1 ，否则相当于没有回溯。

当k=-1的时候，表示找不到这种最长前缀。

用公式表示为

当k=-1的时候，表示空串。

p表示模式串。

以下举一个计算next数组的样例，如果模式串是 “ abaabcaba” 。

以 j = 8 为例，最长前缀为aba，最后一个字符位置为2，故 next[8] = 2 。

那么怎样高速求解next数组呢？

这里有点动态规划的思想在里面。当中位置 j 等于 0 的 next 值为-1，表示找不到这种最长前缀。

j > 0 时。next值能够通过 j - 1 位置的next值求得。

求解next[ j ]的步骤： t =next[ j - 1 ] + 1，t 指向可能等于 p[ j ] 的位置，即 p[ t ] 可能等于 p[ j ]。假设 p[ t ] = p[ j ] ， 那么 next[ j ] = next[ j - 1 ] + 1假设p[ t ] != p[ j ] ， 则令 t = next[ t - 1 ] + 1，继续第 2 步直到 t = 0 或者找到位置。结束时推断p[ t ] 是否等于 p[ j ] ，假设等于则 next[ j ] = t 。 否则等于 -1 。

下图表示了第一次不匹配。第二次匹配的过程，其他过程能够类推。当中或 覆盖部分表示最长匹配串。

为待判定位置， 为已判定位置。

0123 j ×××××××××××××××××××××××××××××××××××××××××

×××××××××××××××××××××××××××××××××××××××××

2）利用next数组进行最小回溯

s××××××××××××××××××××××××××××××××××××××××××××

p ××××××××××××××

在j处不失配时，前面的有部分匹配，这时须要利用next数组信息进行最小回溯。

s××××××××××××××××××××××××××××××××××××××××××××

p ××××××××××××××

（这里 i 指向 s ， j 指向 p。）

注意在 j = 0 的时候失配时。直接 i++ 就可以。

当 j > 0 的时候。须要利用next数组最快找到 p[ j ] == s[ i ] 的位置。

假设 j 移动到了0还找不到。则 i++，然后继续匹配。

这里我们能够发现仅仅有j 回溯了，i没有回溯，可是因为普通版本号的 KMP 算法 j 须要不停地回溯直到找到合适的回溯位置，因此速度不是特别快，还能够继续优化，感兴趣的读者能够想想怎样事先求解好next数组从而不须要不停地回溯。

代码实现

strStr返回的是首次匹配的地址，假设不能匹配则返回NULL。

class Solution {public:vector<int> getNext(char* &s){vector<int> next(strlen(s), -1);for(int i=1; i<strlen(s); i++){int j = next[i-1]; /* 前一个字符的最长匹配长度 */while(s[j+1] != s[i] && j>=0) j = next[j];if(s[j+1] == s[i]) next[i] = j+1;// else 默觉得-1}return next;}char *strStr(char *haystack, char *needle) {if(haystack==NULL || needle==NULL) return NULL;if(strlen(haystack) < strlen(needle)) return NULL;if(strlen(needle) == 0) return haystack;vector<int> next = getNext(needle);int i = 0;int j = 0;int haystackLen = strlen(haystack);int needleLen = strlen(needle);while(i<haystackLen && j<needleLen){if(haystack[i] == needle[j] ) {i++;j++;if(j == needleLen) return haystack + i - j;}else{if(j == 0) i++;else j = next[j-1]+1; /* 该步骤能够优化 */}}return NULL;}};

因为有人问有没有java版本号的，因为鄙人java比較挫，写java时部分还写成了scala的语法。不知道代码是否规范，有优化的地方还麻烦java方面的大神指点。

import java.util.*;public class StrStrSolution {private List<Integer> getNext(String p){List<Integer> next = new ArrayList<Integer>();next.add(-1);for(int i=1; i<p.length(); i++){int j = next.get(i-1);while(p.charAt(j+1) != p.charAt(i) && j>=0) j = next.get(j);if(p.charAt(j+1) == p.charAt(i)) next.add( j + 1 );elsenext.add( -1 ); }return next;}public String strStr(String haystack, String needle) {if (haystack == null || needle == null) return null;if (needle.length() == 0) return haystack;if (needle.length() > haystack.length()) return null;List<Integer> next = getNext(needle); int i = 0; int j = 0;int haystackLen = haystack.length();int needleLen = needle.length(); while(i < haystackLen && j < needleLen){ if(haystack.charAt(i) == needle.charAt(j) ) { i++; j++; if(j == needleLen) return haystack.substring(i - j); }else{ if(j==0) i++; else j = next.get(j-1)+1; } } return null;}public static void main(String[] args) {String s = "babcabaabcacbac";String p = "abaabcac";StrStrSolution sol = new StrStrSolution();System.out.println(sol.strStr(s,p)); }}

版权声明：本文博主原创文章。博客，未经同意，。

如果觉得《【数据结构amp;amp;等差数列】KMP简介和算法的实现（c++ amp;amp; java）》对你有帮助，请点赞、收藏，并留下你的观点哦！