KMP模式匹配算法
1、前缀和后缀
前缀指除了最后一个字符以外，一个字符串的全部头部组合，如：对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}。
后缀指除了第一个字符以外，一个字符串的全部尾部组合，对于字符串”ababa”，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}。
2、PMT数组
PMT数组是一个被称为部分匹配表的数组，PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度，如：对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。
PMT数组的首位通常设置为0，求PMT数组的时候，对于模式串的位置j，考察patten[j]，查找字符串patten[j]的最大相等的前缀和后缀，假设最大相等前缀和后缀长度为k，则有k使得 p[0]p[1]p[2]......p[k-2]p[k-1] = p[j-k+1]......p[j-1]p[j]。
生成PMT数组的程序：
//生成PMT
void makePMT(const char p[], int pmt[])
{
int q, k;//q:模版字符串下标；k:最大前后缀长度
int m = strlen(p);//模版字符串长度
pmt[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
for (q = 1, k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的pmt值
{
while (k > 0 && p[q] != p[k]) // 递归的求出P[0]···P[q]的最大的相同的前后缀长度k
k = pmt[k-1];
if (p[q] == p[k])//如果相等，那么最大相同前后缀长度加1
{
k++;
}
pmt[q] = k;
}
}为了编程的方便， 通常不直接使用PMT数组，而是将PMT数组向后偏移一位，新得到的这个数组称为next数组。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。
3、Next数组
Next数组的首位通常设置为-1，求next数组的时候，对于模式串的位置j，考察patten[j-1]，查找字符串patten[j-1]的最大相等的前缀和后缀，假设最大相等前缀和后缀长度为k，则有k使得 p[0]p[1]p[2]......p[k-2]p[k-1] = p[j-k]p[j-k+1]......p[j-2]p[j-1]。
生成Next数组的程序：
//生成Next
void makeNext(const char p[], int next[])
{
next[0] = -1;
int i = 0, j = -1;
int m = strlen(p);
while (i < m)
{
if (j == -1 || p[i] == p[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}4、KMP匹配算法
KMP模式匹配算法其实就是利用部分已经匹配的有效信息，保持主串坐标不回溯，通过修改模式串的坐标，是模式串尽量移动到有效位置。KMP模式匹配算法的关键就在于Next数组。
KMP模式匹配算法的代码实现：
int KMP(const char t[], const char p[], int next[])
{
int i = 0, j = 0;
int m = strlen(p), n = strlen(t);
while (i < n)
{
if (j == -1 || t[i] == p[j])//// 当j为-1时，要移动的是i，当然j也要归0
{
++i; ++j;
}
else
j = next[j];
if (j == m) {
return i - m;
break;
}
}
return -1;
}5、KMP算法改进
KMP模式匹配算法改进的重点在于对Next数组的改进，即生成Nextval数组。
从Next数组得到Nextval数组，对于模式串的位置i，若next[i+1]=next[i]+1，则nextval[i]=nextval[next[i]]，0<=i<=strlen(p)-1；否则nextval[i] = next[i]。改进过的KMP算法，它是在计算next值的同时，如果a位字符与它的next值执行的b位字符相等，则该a位的nextval值等于b位的nextval值，如果不等，该a位的nextval值就是它自己a位的next值。
生成Next_val数组代码：
void makeNextval(const char p[],int next_val[])
{
next_val[0] = -1;
int i = 0, j = -1;
int m = strlen(p);
while (i < m)
{
if (j ==-1 || p[i] == p[j])
{
++i;
++j;
next_val[i] = (p[i] != p[j] ? j : next_val[j]);
}
else
j = next_val[j];
}
}