KMP算法是字符串的匹配算法，比如我给一个名为《文本》的字符串，和一个名为《样板》的字符串，询问《样板》在《文本》中出现过的次数，这就需要字符串匹配算法。对于匹配，形象一点可以看例子：
《文本1》="abcdefghigklmn"
《样板1》="abc"
=============================
《文本2》="abcdefghigklmn"
《样板2》="abcabcabcabcabcabc"
这两个例子，显然例1才是正确的，因为如果样板的长度大于文本的长度，永远无法匹配，所以匹配就没有意义。因此，如果给定文本的长度，则样板的长度一定要小于等于它，即
// 如果
0 < strlen(text) <= n;
0 < strlen(pattern) <= m;
// 那么一定有
m <= n;
要解决匹配问题，最容易想到的就是朴素匹配法，也就是所谓的暴力匹配。
它的做法是从样板的第一个字符一个一个匹配，如果匹配上，则检查样板第二个字符是否匹配，直到完全匹配或者不匹配。如果出现不匹配，那么样板将从文本的第二个字符开始检查，以此类推。例如：
| 123456789 | 123456789 | 123456789 | 123456789 |
+------------+-------------+-------------+-------------+
| bcabasgfd | bcabasgfd | bcabasgfd | bcabasgfd |
| | | | | |||| | | |
| * | * | ^^^* | * |
| abac | abac | abac | abac |
它唯一的优点就是容易想到，并且容易实现。缺点就是太慢了，以及“时间复杂度”和“空间复杂度”这样的概念，这似乎是优化算法时常用的概念，但是这不是我现在学习的重点，所以不管。
KMP算法的优点在于充分利用了样板pattern的信息，仍然拿上面的字符串举例子：第一次比较一个字符也没匹配上，下次比较，pattern就应该左移一位；第二次同样；第三次匹配到三个字符，第四个字符不匹配，接下来该怎么移动？和暴力匹配一样，把pattern移到第4位置吗？
KMP算法说，或许不需要，或许在这里可以节省时间。
| 123456789 | 123456789 | 123456789 | 123456789 |
+------------+-------------+-------------+-------------+
| bcabasgfd | bcabasgfd | bcabasgfd | bcabasgfd |
| | | | | |||| | || |
| * | * | ^^^* | ^* |
| abac | abac | abac | abac |
因为第三次比较时已经匹配上了aba这三个字符，所以不需要移动，我们就知道第4位是b，第5位是a。因此下一次可以直接把pattern移到第5位，而不是第4位。
果然节省了时间；我们首先使用了“匹配数”，是3；然后根据匹配数就能在pattern中找到aba；由于aba的后缀a和pattern或者说aba的前缀a相等，我们跳过了中间的b移动到了a，也就是跳过4位置，到达5位置。
这种想法怎么实现呢？
答案是利用样板pattern制作一个部分匹配表。比如abac，它的部分匹配表是：
匹配数对应一个匹配值，它的特点是只需要一个pattern就能构造，也就是匹配之前生成的。
它的用法是这样的
// 下次的位移 s'；匹配数 i；匹配值PI[i]；
s' = i - PI[i];
当pattern与文本达到对应的匹配数之后，下一次移动的位置就用上面的公式计算。继续看上面的例子：
| 123456789 | 123456789 | 123456789 | 123456789 |
+------------+-------------+-------------+-------------+
| bcabasgfd | bcabasgfd | bcabasgfd | bcabasgfd |
| | | | | |||| | || |
| * | * | ^^^* | ^* |
| abac | abac | abac | abac |
在第三步，匹配数是3，对应的匹配值是1，下一次的移动位数是3-1=2，也就是下一次的匹配位置是3+2=5，和前面的看法一致。
根据算法可以写出代码（输出和注释非常详细）：
#include <stdio.h>
#include <string.h>
// 字符串的KMP算法，用于字符串样板P与待比较字符串的匹配
// 样板P的前缀函数，用于生成样板P的《部分匹配表》
// 不要让函数改动 P字符数组 ，使用const
int PAI (const char * a)
{
// 用于部分匹配表的输出，保存pai值的数组
int pi[strlen(a)];
pi[0]=0;
// 关键在于，计算样板P的，不同匹配数下的，前缀和后缀的最大共同长度
// 匹配数从0到样板P的最大长度时，匹配到的字符串，长度当然是从0到样板P的最大长度
// for循环，用于递增匹配数
// 从第一位字符开始，因为i从0开始，因此大小是匹配数-1
// 这时候字符长度是 i+1
for (int i=0;i<strlen(a);i++)
{
printf("========================本轮的匹配数i=%d========================\n",i+1);
// 用于保存部分匹配数
int pai=0;
// 当i到达匹配数对应的字符时，计算这个字符串前缀和后缀的最大共同长度
// 所谓前缀后缀可以取很长，例如abcdefg的前缀最长是 abcdef，后缀最长是bcdefg
// while循环结束之后就能输出字符串前缀和后缀的最大共同长度，也就是部分匹配数
// k代表前缀和后缀的长度，长度每轮循环+1
int k=0;
while (k<i)
{
// 计数器
// 每次遍历大一位前缀时计数器清空
int m=0;
// 上来就给k+1，符合实际，也方便循环条件比较
k++;
printf("********本次的前缀长度为%d********\n",k);
// 使用for循环，循环k次，即遍历前缀或者后缀
for (int n=0;n<k;n++)
{
// 前缀的第一个字符与后缀的第一个字符比较。。。
printf("前缀第%d个字符a[%d]是：%c\n",n+1,n,a[n]);
printf("后缀第%d个字符a[%d]是： %c\n",n+1,i-k+n,a[i+1-k+n]);
// 也就是p[0]与p[i-1-k]， p[1]与p[i-k+1]...p[i-1-1]与p[i-1]，从这里也能看出k=i-1
// 因此使用while (k<i)没问题
// 如果相等，计数器+1
if (a[n]==a[i+1-k+n])
{
printf("----->第%d个字符相等，是%c\n",n+1,a[n]);
m++;
// 如果计数器大小等于k，即前缀和后缀每一项都相等，赋值给pai
if (m==k)
{
pai=m;
}
}
}
}
printf("部分匹配数pi=%d\n",pai);
pi[i]=pai;
}
// 输出一个部分匹配表
printf("=====部分匹配数表=====\n");
for (int i=0;i<strlen(a);i++)
{
printf("PI[%2d]=%2d\n",i+1,pi[i]);
}
}
int main ()
{
//char p[]="ABCDABD";
//char p[]="ababababca";
char p[]="abac";
PAI(p);
return 0;
}
下面这个是使用KMP算法进行匹配的代码，根据输出可以看出，一共比较了33次，如果是暴力算法将要比较38次 ，相比之下确实减少了比较次数。
#include <stdio.h>
#include <string.h>
void PAI (const char * a,int *pi)
{
pi[0]=0;
for (int i=0;i<strlen(a);i++)
{
int pai=0;
int k=0;
while (k<i)
{
int m=0;
k++;
for (int n=0;n<k;n++)
{
if (a[n]==a[i+1-k+n])
{
m++;
if (m==k)
{
pai=m;
}
}
}
}
pi[i]=pai;
}
}
// 计算字符串q
int main ()
{
char p[]="aba";
char q[]="casvabcvbuyabaodgaababcasaigdyavgcgdhaba";
int pi[strlen(p)];
PAI(p,pi);
printf("文本长度%d，样板长度%d\n",strlen(q),strlen(p));
// 样板的末尾不要超出文本
{
// 记录文本的出现次数
int m=0;
// 记录样板在字符串的位置
int s=0;
while(s<=strlen(q)-strlen(p))
{
// 记录匹配数
int n=0;
// 当p[0]==q[s]开始匹配
if (p[0]==q[s])
{
printf("第一个字符匹配，现在位置是：%d\n",s);
n++;
// 开始从样板的第二个字符匹配
for (int i=1;i<strlen(p);i++)
{
// 匹配上则匹配数+1
if (p[i]==q[s+i])
{
printf("第%d个字符匹配\n",i+1);
n++;
// 计数
if (n==strlen(p)) m++;
}
}
printf("一共匹配%d个字符\n",n);
// 下一次的移动步数利用公式给出，数组从0开始，所以是pi[n-1]
s=s+n-pi[n-1];
}
// 第一个就不匹配，移动到下一个位置
else
{
s++;
}
}
// 输出样板出现次数
printf("样板出现%d次",m);
}
return 0;
}
本次学习主要参考站内两位大佬的博客
这位大佬的博客专业性很强，很细，有点难看懂，但是硬看下来的话就觉得都很清楚：
https://www.cnblogs.com/gaochundong/p/string_matching.html
这位大佬把KMP说得很简洁，也有很多图片，很形象，很容易看懂，并且也是C语言：
https://www.cnblogs.com/maybe2030/p/4633153.html