Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
KMP算法对比暴力匹配算法的优势是：KMP算法通过分析模式串，找出模式串中相同的前缀和后缀，这样在匹配失败，移动模式串的时候，避免一些重复性的工作。
KMP算法的流程是：
- 文本串S匹配到位置i，模式串P匹配到位置j
- 如果j == -1，或者当前字符匹配成功，即S[i] == P[j]，令i++，j++，继续匹配下一个字符
- 如果j != -1，且当前字符不匹配，即S[i] != P[j]，令i不变，j = next[j]。
可以看出，kmp算法的关键在于计算出Next数组。
next数组对应的是模式串P。对next数组计算过程的理解，类似于归纳分析法。next数组中每一个元素的值，表示模式串P中该元素对应的字符前面的子字符串（不包括该位置的字符）中相同的前缀和后缀的长度。
令
next[0] = -1
next[j] = k
- 如果P[k] == P[j]，则next[j+1] = next[j] + 1 = k + 1
- 如果P[k] != P[j]，进行递归运算，如果P[next[k]] == P[j]，则next[j + 1] = next[k] + 1，否则继续递归。
这是c版本的，别人的：
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
}
我自己写了一个Erlang版本的：
-module(kmp).
-compile([export_all]).
get_next(Pattern) ->
Next = [-1],
K = -1,
J = 0,
do_while(K, J, Next, Pattern).
do_while(_K, J, Next, Pattern) when J >= length(Pattern) - 1->
Next;
do_while(K, J, Next, Pattern) ->
case K =:= -1 orelse lists:nth(J + 1, Pattern) =:= lists:nth(K + 1, Pattern) of
true ->
K1 = K + 1,
J1 = J + 1,
NewNext = lists:append(Next, [K1]),
do_while(K1, J1, NewNext, Pattern);
false ->
K1 = lists:nth(K + 1, Next),
do_while(K1, J, Next, Pattern)
end.
kmpSearch(String, Pattern) ->
SLen = length(String),
PLen = length(Pattern),
Next = get_next(Pattern),
{SEnd, PEnd} = do_search(0, 0, SLen, PLen, String, Pattern, Next),
Index = if PEnd =:= PLen ->
SEnd - PEnd;
true ->
-1
end,
Index.
do_search(I, J, SLen, PLen, String, Pattern, Next) when I < SLen , J < PLen ->
case J =:= -1 orelse lists:nth(I + 1, String) =:= lists:nth(J + 1, Pattern) of
true ->
I1 = I + 1,
J1 = J + 1,
do_search(I1, J1, SLen, PLen, String, Pattern, Next);
false ->
J1 = lists:nth(J + 1, Next),
do_search(I, J1, SLen, PLen, String, Pattern, Next)
end;
do_search(I, J, _SLen, _PLen, _String, _Pattern, _Next) ->
{I, J}.
参考：