串的模式匹配算法（C语言）
1.字符串的初始化函数
定义一个字符数组S，我们用第0位来存储该字符串的长度，其余位置顺序存储该字符串。（字符串的首位从1开始）
代码实例：
#include <stdio.h>
#include <string.h>
#define N 100 /*静态定义数组的长度*/
typedef char String[N]; // String s1 等价于 char s1[N]
int StrAssign(String T, char *chars) // 初始化字符串
{
T[0] = strlen(chars);
for (int i = 1; i <= strlen(chars); i ++ ) {
T[i] = *(chars + i - 1);
}
return 1;
}
int main()
{
String s1;
StrAssign(s1, "hello world!");
printf("%s", s1); // 输出该字符串
printf("\n%d", s1[0]); // 输出字符串的长度
return 0;
}
2.朴素模式匹配算法
思想：
从主串S的第pos位开始逐位与模式串T比较，若对应位置的字符均相等，则匹配成功，返回模式串T在主串S中的位置，否则模式串T整体向后移动一位重新从头开始比较（例如，当前是从主串S的第pos位与模式串T的第1位开始比较，则下一次就是主串S的第pos+1位与模式串T的第1位开始比较），直到匹配成功或无法再继续匹配（主串S剩余未被匹配的长度小于模式串T的长度）。
若匹配成功，返回模式串T在主串中的位置；否则返回0
代码实例：
#include <stdio.h>
#include <string.h>
#define N 100
typedef char String[N + 1];
int StrAssign(String T, char *chars) /*初始化字符串*/
{
T[0] = strlen(chars);
for (int i = 1; i <= strlen(chars); i ++ ) {
T[i] = *(chars + i - 1);
}
return 1;
}
/*返回子串T在主串S中第pos个字符之后的位置，若不存在，则返回0*/
int Index(char S[], char T[], int pos)
{
int i = pos; // i用于主串中当前位置下标
int j = 1; // j用于字串T中当前位置下彪
while (i <= S[0] && j <= T[0]) { // 若i小于S 且 j小于T的长度时循环
if (S[i] == T[j]) { // 两字符相等这则继续
i++;
j++;
}
else {
i = i - j + 2; // 回到上一次匹配位置的下一位
j = 1;
}
}
if (j > T[0]) return i - T[0]; // j>T[0]说明匹配成功
else return 0;
}
int main()
{
String s1, s2;
StrAssign(s1, "abcccdef");
StrAssign(s2, "cd");
printf("%d", Index(s1, s2, 1));
return 0;
}
3.KMP模式匹配算法
朴素模式匹配算法的低效性：
通过朴素模式匹配算法我们可以知道，当主串S为：abcdefghijk… ，模式串T为：abcdek 时，假设我们从S的第一位开始比较，则前5位字符均相等，第6位字符不等，按照朴素模式匹配的思路，我们此时应该从S的第2位字符’b’（S[2]）开始重新与T的第一位’a’（T[1]）比较，不等，然后让S[1]与T[1]比较，还是不等… 对于T来说，T[1]与后面的’bcdek’均不等，那么如果T的前五位都与S的前五位相等，而T[1]与T[2]、T[3]、T[4]都不相等，则T[1]与S[2]、S[3]、S[4]也不等，这些比较都是无效的比较，是算法可以优化的地方。
下面看T[1]与T后面的字符相等的情况，假设主串S为：abcababca ，模式串T为：abcabx ，我们可以看到，S与T的前5位都相同，第6位不同，且T[1]与T[2]、T[3]不相同，那么T[1]与S[2]、S[3]也不相同，可以直接跳过这些步骤，从S[4]与T[1]开始比较。 又因为T[1]（a）与T[4]（a）相等，T[2]（b）与T[5]（b）相等，且而 T的前五位与S的前五位相等（自然T[4]T[5]（ab）与S[4]S[5]相等）。 那么可以推出：T[1]T[2]与S[4]S[5]也是相同的，我们可以直接从T[3]与S[6]开始比较。 我们可以发现在上述的比较过程中，主串S的比较位置并没有回溯，我们先从S[1]–S[5]与T[1]–T[5]进行比较，然后直接从T[6]与T[3]进行比较。这种方法就是KMP模式匹配算法。
从上面的例子我们知道，在KMP算法中，主串S的比较位置是不进行回溯的，相当于我们在比较的过程中主串不动，不断移动模式串T，例如在刚才的例子中，当S[6]与T[6]不相等时，我们通过推算，将模式串T向后移动了3个单位，让T[3]来与S[6]比较，在KMP算法中，存在一个next数组，用来记录在模式串T中每个字符的回溯位置，next数组中的值与主串S无关， 经过计算，next[6] = 3，所以当第6个位置不匹配时，我们直接将模式串T回溯到第三位继续匹配。那如何计算next数组的值呢？
3-1.手推next数组
以模式串T=ababaaaba 为例，j表示字符串T中字符的位置，下方红色部分为next数组计算的方法。
3-2.next数组代码实例
我们仍求ababaaaba的next数组，程序的结构为：0 1 1 2 3 4 2 2 3，与我们在上面手推的结果是一致的。
#include <stdio.h>
#include <string.h>
#define N 100
typedef char String[N]; // String s1 等价于 char s1[N]
int StrAssign(String T, char *chars) // 初始化字符串
{
T[0] = strlen(chars);
for (int i = 1; i <= strlen(chars); i ++ ) {
T[i] = *(chars + i - 1);
}
return 1;
}
// 返回字串T的next数组
void get_next(String T, int *next)
{
int i, j;
i = 1;
j = 0;
next[1] = 0;
while (i < T[0]) { // T[0]为串T的长度
if (j == 0 || T[i] == T[j]) { // T[i]表示后缀的单个字符，T[j]表示前缀的单个字符
i++;
j++;
next[i] = j;
}
else
j = next[j]; // 若字符不相等，则j值回溯
}
}
int main()
{
String T;
int next[N] = {0};
StrAssign(T, "ababaaaba");
get_next(T, next);
for (int i = 1; i <= T[0]; i ++ ) {
printf("%d ", next[i]);
}
return 0;
}
3-3.KMP算法实例
求字串 aba 在 主串 ababaaaba 第4个位置后 首次出现的位置，程序输出结果为7。
#include <stdio.h>
#include <string.h>
#define N 100
typedef char String[N]; // String s1 等价于 char s1[N]
int StrAssign(String T, char *chars) // 初始化字符串
{
T[0] = strlen(chars);
for (int i = 1; i <= strlen(chars); i ++ ) {
T[i] = *(chars + i - 1);
}
return 1;
}
// 返回字串T的next数组
void get_next(String T, int *next)
{
int i, j;
i = 1;
j = 0;
next[1] = 0;
while (i < T[0]) { // T[0]为串T的长度
if (j == 0 || T[i] == T[j]) { // T[i]表示后缀的单个字符，T[j]表示前缀的单个字符
i++;
j++;
next[i] = j;
}
else
j = next[j]; // 若字符不相等，则j值回溯
}
}
// 返回字串T在主串S中的第pos个字符之后的位置，若不存在则返回0
int Index_KMP(String S, String T, int pos)
{
int i, j;
i = pos; // i用来表示主串S当前位置的下标值
j = 1; // j用来表示字串T当前位置的下标值
int next[255];
get_next(T, next); // 对字串T做分析，求出T的next数组
while (i <= S[0] && j <= T[0]) { // 当i小于S的长度 且 j小于T的长度时，循环继续
if (j == 0 || S[i] == T[j]) {
i++;
j++;
}
else {
j = next[j]; // j退回到合适的位置，i值不变
}
}
if (j > T[0]) return i - T[0];
else return 0;
}
int main()
{
String S;
String T;
StrAssign(S, "ababaaaba");
StrAssign(T, "aba");
printf("%d", Index_KMP(S, T, 4));
return 0;
}
3-4.nextval数组的求解
我们现在已经知道了KMP算法的求解思想，来看这样一个例子：
假设主串S为 aaaabcde ，字串T为 aaaaax ，我们要匹配T在S中首次出现的位置，用 i 表示主串S当前字符的位置，用 j 表示字串T当前字符的位置。
首先算出T的next数组为 ：
| j | j = 1 | j = 2 | j = 3 | j = 4 | j = 5 | j = 6 |
|---|---|---|---|---|---|---|
| next[j] | 0 | 1 | 2 | 3 | 4 | 5 |
当 i = 5 ，j = 5 时，S[5] = b , T[5] = a，不相等。按照刚才KMP的思路，此时应让j = next[j] = next[5] = 4, 也就是让j回溯到4，再与S[5]进行比较，发现又不等，j回溯到3，还是不等，j回溯到2, 还是不等，j回溯到1，还是不等。此时 i++，i 变成 6 ，再与 j = 1 开始比较。我们发现因为字串T的第1到5位都是相等的，当第T[5]与S[5]不相等时，T[4]、T[3]、T[2]、T[1]也必然与S[5]不相等，这里的比较也是多余的操作。我们对求next数组的函数进行优化，将新的值存在nextval数组中。
优化的思路是：
在原来用next数组进行回溯时，如果回溯位置t1的字符与原字符相等，那么直接回溯到t1的next数组的值t2，若t2位置的字符与原字符也相等，则继续回溯到t2的next数组的值t3，直到该字符与原字符不相等。
我们以串T ababaaaba为例，求它的nextval数组：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| T | a | b | a | b | a | a | a | b | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 |
当 j = 1 时，nextval[1] = 0；
当 j = 2 时，T[2] = b，next[2] = 1，而T[1] = a，与b不相等，所以 nextval[2] = next[2] = 1；
当 j = 3 时，T[3] = a，next[3] = 1, 因为T[1] ==T[3]，所以nextval[3] = nextval[1] = 0；
…
当 j = 9 时，T[9] = a, next[9] = 3, 而3位置的字符也是a，所以nextval[9] = nextval[3] = 0；
3-5.nextval数组代码实例
以字符串 ababaaaba为例，程序的输出结果为 0 1 0 1 0 4 2 1 0
#include <stdio.h>
#include <string.h>
#define N 100
typedef char String[N]; // String s1 等价于 char s1[N]
int StrAssign(String T, char *chars) // 初始化字符串
{
T[0] = strlen(chars);
for (int i = 1; i <= strlen(chars); i ++ ) {
T[i] = *(chars + i - 1);
}
return 1;
}
// 返回字串T的nextval数组
void get_nextval(String T, int *nextval)
{
int i, j;
i = 1;
j = 0;
nextval[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
i++;
j++;
if (T[i] != T[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else {
j = nextval[j]; // j值回溯
}
}
}
int main()
{
String S;
StrAssign(S, "ababaaaba");
int nextval[100];
get_nextval(S, nextval);
for (int i = 1; i <= S[0]; i ++ )
printf("%d ", nextval[i]);
return 0;
}
改进过后的KMP算法只需将get_next函数 替换为 get_nextval函数即可。
内容参考：
《大话数据结构》程杰