本文主要是介绍KMP算法之我见（初解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
几天前看到KMP算法的时候，头大如麻，略读一遍，决定跳过，学完了整章串、数组、矩阵和广义表之后回头专心研究KMP算法。
在学习这本《数据结构》的前几章的时候我就开始对这本教程有点失望了，当初在图书馆里对比了十几本教程选择了它，主要原因是它图解较多，便于理解，但是细读发现它的代码不够讲究，实用性不强，可能是我经验匮乏吧，反正这本教材的堆栈部分我很不满意，代码可用性太小，相较其他版本的结构体实现堆栈劣势明显。言归正传，因上述原因，我没有再研究本书，而是看了视频教程，小甲鱼的教程让我对NEXT数组有了直观认识，但是在后来的NEXT数组的实现和KMP算法优化上依然云雾缭绕。
NEXT数组核心思想：
当前匹配点失配，模式串该前进几位与当前的主串匹配点重新进行比较，而NEXT数组元素值就是前进的位数。假设模式串在p9点失配，则p0p1p2p3p4p4p5p6p7p8与当前对应的主串字符是一一相等的，下一步改用模式串第几位取代P9位重新对比呢，关键看p0p1p2p3p4p4p5p6p7p8的前缀子串和后缀子串，前后缀子串分别对应为：
P0 —— P8
P0P1 —— P7P8
P0P1P2 —— P6P7P8
……
P0P1P2P3P4P5P6P7 —— P1P2P3P4P5P6P7P8
分别判断这些前缀子串后缀子串对是否相等，如果相等，下一次匹配的时候，就用前缀子串的取代后缀子串的位置，即模式串整体前进了strlen(前后缀子串)个位数.
有了这个思路，就开始通过代码实现NEXT数组的求值。
（事实上这个思路过程有些繁琐，所以牵扯到后续的优化问题，后话暂且不提）
NEXT数组求法，及测试函数如下：
//测试：-1 0 0 0 1 2 3 4 5 0 1 abcabcabbac
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 12
int FindNext(char *t,char x);
int main()
{
char str[MAX] = "abcabcabbac";
char x; //失配点
printf("当前模式串：%s \nNEXT数组求值过程如下：\n\n",str);
for(x=0;x<MAX-1;x++)
{
printf("next[%d] = %d \n\n",x,FindNext(str,x));
}
return 0;
}
//传入一个模式串t，t串当前失配点字符位置x，返回next值，默认数组长度宏定义MAX
int FindNext(char* t,char p)
{
char i,j;
char qtr[MAX];
char ptr[MAX];
char n=0;
char k=0;
if(p==0)
{
return -1;
}
for(i=0;i<p-1;i++)
{
//处理前缀子串
for(k=0;k<=i;k++)
{
qtr[k] = t[k];
}
qtr[k]='\0';
//处理后缀子串
k=0;
for(j=p-i-1;j<=p-1;j++)
{
ptr[k] = t[j];
k++;
}
ptr[k]='\0';
printf("前缀子串:%-15s 后缀子串:%-15s\n",qtr,ptr);
if(strcmp(qtr,ptr)==0) n=strlen(qtr);
}
return n;
}
能求出NEXT数组，接下来就是利用NEXT数组值进行KMP算法。
思路关键如下：
设主串为ZHU_STR[100]，模式串为MO_STR[10]，则从ZHU_STR[0] == MO_STR[0] ？开始比较，相等，则两串同时前进一位i，对比各串的第二个字符，若不等，则当前匹配点为失配点，根据NEXT数组值向前移动模式串，则主串当前点对应到新的模式串字符，重新判这两个字符相等与否，重复上述过程。
把握住，每一次对比只有两个字符，且只有两种结果，等或不等，等该怎样？（同时前进对比下一位）不等该怎样？（模式串前进）
实现代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 12
int FindNext(char *t,char x);
int main()
{
char z_str[] = "asfsabc";
char m_str[] = "abc";
char z_num=0; //主串当前匹配点
char m_num=0; //模式串当前匹配点
char len_z = strlen(z_str);
char len_m = strlen(m_str);
char p=0; //模式串失配点
char i=0;
while(z_num<len_z && m_num < len_m) //依次用主串的每一个字符和子串对比，主串不回溯
{ //每次对比区别为子串的前进位数,每一次对比只有两种结果
if(z_str[z_num] == m_str[m_num] ) //相同则，同时+1，
{
z_num++;
m_num++;
}
else //不同则，调用NEXT数组决定下一步子串前进多少个字符
{
p = m_num;
i = FindNext(m_str,p);
if(i==-1) //next数组为-1，则子串置0重头来，主串+1（理解如下）
{ //假设模式串p[0]前一位为p[-1],下一次比较要让p[-1]与当前匹配点比较
m_num = 0; //那不就是主串前进一步和p[0]进行对位匹配么。
z_num++;
}
else //否则，主串不变，子串向前滑动相应的位数
m_num = i;
}
if(m_num == len_m)
}
if(m_num == len_m)
{
printf("成功匹配！\n起始位置是：%d\n",z_num-len_m);
}
else
{
printf("没有匹配成功！\n");
}
return 0;
}
//传入一个模式串t，t串当前失配点字符位置x，返回next值，默认数组长度宏定义MAX
int FindNext(char* t,char p)
{
char i,j;
char qtr[MAX];
char ptr[MAX];
char n=0;
char k=0;
if(p==0)
{
return -1;
}
for(i=0;i<p-1;i++)
{
//处理前缀子串
for(k=0;k<=i;k++)
{
qtr[k] = t[k];
}
qtr[k]='\0';
//处理后缀子串
k=0;
for(j=p-i-1;j<=p-1;j++)
{
ptr[k] = t[j];
k++;
}
ptr[k]='\0';
if(strcmp(qtr,ptr)==0) n=strlen(qtr);
}
return n;
}
KMP算法实现总结：
1、写next数组的时候就失误了，每次传回的是一个元素值，而不是一个数组，导致主函数执行是不停调用子函数去求NEXT值做出反应，应该让NEXT函数只运行一次返回一个整个的NEXT数组供主函数查找，这样简化了很多步奏。
2、NEXT数组的求法上过于繁琐，有待研究之后下期博文优化改进。
3、感觉程序思路好像还算明白，但是相对其他的KMP算法实现代码量大了不少。这篇关于KMP算法之我见（初解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
