目录
1.串的简单模式匹配——BF
串的模式匹配就是子串定位操作，给定两个串s="s₀s₁.....sₙ₋₁"和t="t₀t₁.....tₘ₋₁"（其中n和m分别是串t和串s的长度），在主串s中寻找子串t的过程称为模式匹配。如果在s中找到等于t的子串，则匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1.
下面介绍蛮力（BF）模式匹配算法：
从主串s中下标为0的字符开始，与模式串t中下标为0的字符进行比较，若相同，则继续逐个比较s和t中的后续字符；若不同，则从主串s中下标为1的字符开始，与模式串t中下标为0的字符进行比较。以此类推，重复上述过程，若t中字符全部比较完，则说明匹配成功；否则匹配失败。
设主串s="ababcabcacb"，模式t="abcac"
最好情况的时间复杂度O(n+m)
最坏情况的时间复杂度O(n×m)
2.KMP算法思想
分析BF算法的执行过程，造成BF算法慢的原因是回溯，即在某趟的匹配过程失败后，对于串s要回到本趟开始字符的下一个字符，串t要回到首字符，而这些回溯是不必要的，KMP算法对BF算法的改进之处在于取消了主串的回溯
在第3趟匹配过程中，s₂~s₅和t₀~t₃是匹配成功的，s₆≠t₄匹配失败，因此有了第4趟，其实这一趟是不必要的，因为在第3趟中有s₃=t₁，而t₀≠s₃，就有t₀≠s₃。同样第5趟也没必要，进一步分析第6趟中的第一对字符s₅和t₀也是多余的，因为在第6趟的比较可以从第二对字符s₆和t₁开始进行。这就是说，在第3趟匹配失败后，指针i不动，而是将模式串t向右滑动，用t₁对准s₆继续进行匹配。这样的处理方法指针i是无回溯的。
某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置k上，使得tₖ对准sᵢ继续向右进行
如果模式串中满足式"t₀ t₁....tₖ₋₁"="tⱼ₋ₖ tₖ₋ⱼ₊₁.....tⱼ₋₁"的子串存在，即模式中的前k个字符与模式中tⱼ字符前面的k个字符相等时，模式t就可以向右滑动使tₖ和sᵢ对准，继续向右进行比较
3.模式串next数组及计算
模式中的每一个tⱼ都对应一个k值，用next[j]表示tⱼ对应的k值，next数组定义如下：
首先，求最长前缀表，比如：
abcab的最长前缀是2
abcd的最长前缀是0
abcabc的最长前缀是3
以下图数组为例，下标从0开始，首先把前缀表的第一位赋值为0
然后将p写成如下形式，即将p[0]~p[n](1~8)写出，分别计算最长前缀
然后将结果填入
敲黑板！
上图并不是next数组，而是个前缀表prefix，但是离next数组很近了！只需将prefix数组的最后一个值即p[8]去掉，将p[0]前面加一个-1再整体后移一位，就得到next数组了！
源代码
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
void prefix_table(char p[], int prefix[], int l) {
prefix[0] = 0;
int i = 1;
int len = 0;
while (p[i] != 0) {
if (p[len] == p[i]) {
len++;
prefix[i] = len;
i++;
} else {
if (len > 0) {
len = prefix[len - 1];
} else {
prefix[i] = len;
i++;
}
}
}
}
int main() {
int n = 9;
char p[] = {"ABABCABAA"};
int prefix[9];
prefix_table(p, prefix, n);
for (int i = 0; i < n; i++) {
cout << prefix[i] << endl;
}
return 0;
}运行结果
4.KMP算法
举个例子，设主串s=“ababcabcacb”和模式串t="abcac"来说明KMP算法匹配过程
模式串t="abcac"的next数组值如下：
5.nextval数组——next数组的缺陷和改进
克服不必要重复比较的方法是对next数组的修正，在算法中求得next[j]=k后，要继续判断tₖ和tⱼ是否相等，若相等还要使next[j]=next[k]。修正后的next数组称为nextval数组
例如，已知主串s="aaabaaaab"和模式串t="aaaab"，利用KMP算法进行模式匹配
根据KMP算法，当i=3,j=3时，s₃≠ t₃，由next[j]的指示还需要进行i=3、j=2，i=3、j=1，i=3、j=0等三次比较。实际上，模式串中下标为0、1、2的字符和下标为3的字符都相等，就不需要和主串中 下标为3的字符进行比较，可以将模式一起向右滑动4个字符的位置直接进行i=4、j=0的字符比较
计算nextval的具体过程：
- 第一位的nextval值必定为0，第二位如果与第一位不同则为0，相同则为-1
- 第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则第三位的nextval值为第一位的nextval值，为-1
- 第四位的next值为2，那么将第四位和第二位进行比较，均为a，相同，则第三位的nextval值为第二位的nextval值，为-1
- 第五位的next值为3，那么将第五位和第三位进行比较，不同，则第五位的nextval值为其next值，为3
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
void getnextval(char *t, int nextval[]) {
int j, k, m;
j = 0;
k = -1;
m = strlen(t);
nextval[0] = -1;
cout << "nextval[0]=" << nextval[0] << endl;
while (j < m - 1) {
if (k == -1 || t[j] == t[k]) {
j++;
k++;
if (t[j] != t[k])
nextval[j] = k;
else
nextval[j] = nextval[k];
cout << "nextval[" << j << "]=" << nextval[j] << endl;
} else
k = nextval[k];
}
}
int main() {
int n = 5;
char t[] = {"aaaab"};
int nextval[5];
getnextval(t, nextval);
for (int i = 0; i < n; i++) {
cout << nextval[i] << endl;
}
return 0;
}