世 上 没 有 绝 望 的 处 境 只 有 对 处 境 绝 望 的 人
本文的kmp算法是基于第0位构造的算法，第1位构造的话稍加修改，也是一样的。 字符串匹配算法在数据结构课本中可以看到BF(Brute Force)暴力求解，还有一种相对高效的一种算法KMP算法。博主研究KMP算法也有好几天了，在这过程中，有很多问题。去看别人的博客真的是看的一头雾水，很多文章的大体意思就是，kmp长这样，按这样来就行。不可否认有些博客对我有很大的指导作用，但是这里我讲以自己的理解，去讲解这个KMP(Knuth-Morris-Pratt)算法。
首先想要学习KMP算法，不可避免的一步，那就是学会BF算法。 Brute Force翻译过来就是十分野蛮的暴力寻找。顾名思义，就是以O(nm)的复杂度去暴力去寻找合适的字符串。 下面展示一下
Brute Force Algorithm
#include<stdio.h> #include<string.h> int main() { // 目标:在 T数组中寻找所有可以匹配P的子串 char T[20],P[20]; int ans=0; scanf("%s%s",T,P); for(int i=0; T[i]; i++) { int k=0; for(int j=0; P[j]; j++) if(T[i+j]) { if(T[i+j]==P[j]) k++; else goto NEXT; } else goto NEXT; if(!P[k]) ans++; NEXT: ; } printf("%d\n",ans); return 0; }这段代码展示的匹配过程，可以用下图展示出来。 BF的算法十分的低效，他的复杂度是O(nm)，于是就出现了优化这个过程的算法，KMP算法。 KMP算法是一种优化算法，我们发现在BF的过程中，当匹配失败后，他会移动一位。但是这样，会发现，通常会在下一次移动中不匹配。所以，我们在想可不可以跳过这些无用步骤，只处理可能匹配点。从而实现算法的优化。 首先引入一个概念
最长公共前后缀（Longest common Prefix suffix） 接下来，我们解释一下什么是最长公共前后缀。
最长公共前后缀，是指前缀为该串的真子串，后缀为该串的真子串。这两个子串完全相同，且为所有这类子串中长度最长的子串。 例如：ababa这个字符串的公共前后缀有如下几个关系
a a
ab ba
aba aba
abab baba
其中公共的前后缀只有a a和 aba aba，最长的是aba。 接下来说一个结论 每一次可以移动最长公共前后缀的长度，保证不会遗漏信息 这句话是什么意思呢？对于BF算法而言，他每一次匹配失败都会移动一次，重新进行匹配，这就导致了效率的低下。如果根据这个结论，我们可以以最快的速度来找到匹配位置。现在以一张动态图来模拟一下这个过程。 首先对于已经匹配好的串，如果你稍微移变化一下，一定会不匹配，除非这个串是完全一样的如aaaaa……，那么你需要移动到某个一样的地方，那么这个地方就是对应的最长后缀位置。 所以说，这个结论是正确的。
那么，如果告诉你每一位的最长公共前后缀的话，是不是每一次的不匹配都可以迅速的跳转到应该在的位置。
那么我们的下一步就是求最长公共前后缀 模式串P[]=“ababdababaa”; 那么接下来，我们就求最长公共前后缀 先看一张图： next数组的求法正如上图所示。 其实就是分为两种情况 如果当前指针都匹配，则直接在原基础的情况下加一 如果不匹配那么你就要试着缩小这个最长公共子序列的长度。那么这个缩小其实就是回退到指针所指的位置。那么为什么回退不影响正确结果呢？ next数组的回溯
当前如果相同，那么最长公共子序列的长度加一没有问题。 如果不相同的话，你就要让这个子序列变小。也就是在右半边的后缀和左半边的前缀的下一个最大值。 也就是图片中的这个区间，是第二大的公共前后缀。 因为本来这两块就是公共前后缀(意味着一模一样)，所以这个图也等价于 那么这就转变成求黄色块之前的那个最长公共前后缀了。 所以当蓝色块不匹配的时候，就需要找对应指针(黄色块)之前的最长公共前后缀。 然后就会使得这个黄色块移动位置了。 转变成为这个效果。那么会发现这个匹配了。如果不匹配，就继续昨天的故事，继续找下去。直到找不到为止。 接下来就是如何去构造代码了 KMP algorithm 第一步当然是求next数组了，因为next在C系列的语言中是被当作有含义的字符串，所以，一下用Next表示next数组。 next数组
void Get_next(char* p) { int Next[200] = { 0,0 };//这里第1位和第0位，初始化为0 for (int i = 1, j = 0; p[i]; i++)//当p[i]=='\0'时对应的ascii码是0，所以就会结束 { while (j && p[i] != p[j])j = Next[j];//图中展示步骤 if (p[i] == p[j])j++; Next[i] = j; } }这样我们就得到了next数组。加下来就是用这个next数组了。 怎么用呢？当你当前位置不匹配的时候，你就需要把这个匹配位置移动next数组的地方，这就是一个指针的回调。很简单，代码以看就懂。
#define kmp_size #define kmp_range(j_sta,i_sta,aim) for(int j=j_sta,i=i_sta;aim[i];i++) int kmp(char* t, char* p) { int ans = 0, Next[kmp_size] = { 0,0 }; kmp_range(0, 1, p) { while (j && p[i] != p[j]) j = Next[j]; if (p[i] == p[j])j++; Next[i + 1] = j; } kmp_range(0, 0, t) { while (j && t[i] != p[j])j = Next[j]; if (t[i] == p[j])j++; if (!p[j])ans++; } return ans; }这就是整合后的kmp算法，如果想研究，就可以把这份代码拆开研究一下。 By-轮月
