KMP算法
暴力算法进行对比
假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？
如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符； 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。 理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
}
else
{
//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen)
return i - j;
else
return -1;
}
举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：
- S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）
- S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）
- 直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）
- S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去
- 直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）
- 至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。
而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？
答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置
进入正题—KMP算法
3.1 定义
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
-
核心：KMP算法的核心技术避免
没必要的回溯，回溯问题由模式串决定，不是由目标（主）串决定！~ 暴力破解
~ KMP
~ 没有重复元素时，匹配失败直接从模式串首位开始（i1==j1,i2==j2,因为不重复，即j1!=j2, 所以j1!=i2,同理j1!=i2,3,4，直接将j1和i5比较）
~ 存在重复元素时，移位减少
前后缀和next数组求法：
next为此元素之前的前缀和后缀包含最大元素个数+1， 第一个元素默认为0
前缀：此元素前去掉结尾
后缀：此元素前去掉开头
比较方法：同时从俩端开始比较直到不等
注：next数组再此基础上+1
next数组的结果如下：
-
1.
-
2
? 
、
- 3.
- 4.
NEXT数组：当模式匹配串T施暴后，NEXT数组对应元素知道应该用T串的哪个元素进行下一轮的匹配（*重要）
移位的个数用next代替k数组进行求解，核心代码：
下标代表i，next代表j（匹配失白后可能继续失配，不断回溯直到0）
void get_next( String T, int *next )
{
i = 1;
j = 0;
next[1] = 0;
while( i < T[0] )
{
if( 0==j || T[i] == T[j] )
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j]; //自身回溯
}
}
// 因为前缀是固定的，后缀是相对的。
}
-
完整程序 ：
#include <stdio.h> typedef char* String; void get_next( String T, int *next ) { int j = 0; int i = 1; next[1] = 0; while( i < T[0] )//存放长度 { if( 0 == j || T[i] == T[j] ) { i++; j++; if( T[i] != T[j] ) { next[i] = j; } else { next[i] = next[j]; //优化，加快移动 } } else { j = next[j]; } } } // 返回子串T在主串S第pos个字符之后的位置 // 若不存在，则返回0 int Index_KMP( String S, String T, int pos ) { int i = pos; int j = 1; int next[255]; get_next( T, next ); while( i <= S[0] && j <= T[0] ) { if( 0 == j || S[i] == T[j] ) { i++; j++; } else { j = next[j]; } } if( j > T[0] ) { return i - T[0]; } else { return 0; } } -
通用程序
通过独腿求得next数组：
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]; } } }优化后的next数组方法：
//优化过后的next 数组求法 void GetNextval(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]) { ++j; ++k; //较之前next数组求法，改动在下面4行 if (p[j] != p[k]) next[j] = k; //之前只有这一行 else //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]] next[j] = next[k]; } else { k = next[k]; } } }
KMP的搜索算法 ：
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;
}
