关于串和代码的应用（涉及BF算法、KMP算法）

编写一个能实现顺序串的模式匹配运算的程序（BF和KMP）

1.理解什么是BF算法

BF算法是一种最简单直观的字符串匹配算法。该算法通过穷举主串S的所有模式T，来判断是否与主串S匹配。

模式匹配不一定是从主串的第一个位置开始，可以指定主串中查找的起始位置。

基本思路：

从主串S的查找起始位置的第一个字符开始和模式T中的第一个字符比较，若相等则继续比较下一个字符。若不相等，则从主串的下一个字符开始重新和模式T中的第一个字符比较。

以此类推，如果模式T比较完毕，则说明匹配成功，此时返回模式T第一个字符在主串S中出现的位置。

*重点：若不相等，指针后退重新开始匹配，从主串的下一个字符（i = i - j + 2）起再重新和模式的第一个字符（j = 1）比较。

*为什么是i= i - j + 2？

因为此时已经比较了j-1个字符是相等的，所有从i -（ j- 1 ）+ 1 再比起。

2.BF算法的程序设计

int BF(char *s, char *t) { int i = 0, j = 0; int lens = strlen(s), lent = strlen(t); while (i < lens && j < lent) { if (s[i] == t[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if (j >= lent) return i - j + 1; // 位置从1开始 else return 0; }

*这里为什么传入了指针？

①在C语言中，字符串就是字符数组，数组名本质上就是指针。当你写char s[]作为参数时，编译器实际上把它当作char *s处理。

②传递整个字符串的值效率极低。传入指针的方式可以避免复制整个字符串，并达到了直接操作原字符串的目的。

③strlen是专门用来计算字符串的长度。

3.理解什么是KMP算法

其对于BF算法的改进在于：主串的指针i不回溯，直接从匹配失败的位置开始，继续向右滑动。

设主串S：abaabaabcde，模式T：abaabc

第一次匹配失败后j会回溯到第3个位置开始。

（1）为什么可以让j回溯到第3个位置？

当 i=5, j=5 时字符不等，此时已经匹配的部分 'abaab' 的最长相等前后缀长度为2，说明主串中 i=3,i=4 的字符 'ab' 与模式串前两个字符 'ab' 相等，因此可以直接让 j 回溯到第3个位置继续比较。

（2）如何知道i前面的两个字符和模式T中的前两个字符相等呢？

假设模式T中当前j所指向字符前的所有字符组成的串记成T'，则只需比较T'的前缀和T'的后缀是否相等即可。

以T'＝“abaab”为例，分析如何判断其前缀与后缀是否相等，并得到前后缀相等时的最大长度l_max。

对于上述示例，前后缀相等时的最大长度为2。如果前后缀相等时的最大长度l_max为2，则j可以回溯到3的位置。

归纳：当i和j指向的两个字符不相等时，如果T'的相等前后缀的最大长度为l_max，则i保持不变，j回溯到l_max+1的位置即可。

（3）关于失配

匹配步骤进行会直至下列两种可能：

a. j退到某个next值时字符相等，则指针各自增1，继续进行匹配。

b. j退到值为0，则此时需将模式继续向右滑动一个位置，即从主串的下一个字符s[i]+1起和模式重新开始匹配。

*失配时，i不变，j回退到next[j]重新匹配。当j退到0，i和j需要同时加1

（j退到0：主串的第i个字符和模式的第一个字符不等）

（4）关于nextval

定义的next函数在某些情况下尚有缺陷，会重复比较一些已经比较过确定重复的字符。

所以改进方向是将模式连续右滑，直接比较还没有比较的位置。

这就是说，若按上述定义得到next[j]=k,而模式中t[j]=t[k]，则当主串中字符s[i]和t[j]不等时，不需要再和t[k]进行比较，而直接和t[next[k]]进行比较，此时的next[j]和next[k]相同。

j：当前模式串的位置（失配时在模式串中的位置，t[j] 与主串 s[i] 不等）

k：原 next[j] 的值，表示 j 失配后，下一个要与主串比较的模式串位置（即 k = next[j]）

t[j]：模式串中第 j 个位置的字符

t[k]：模式串中第 k 个位置的字符，其中 k = next[j]

步骤：

1. 先算出原 next[j] = k

2. 比较 t[j] 与 t[k]：

- 如果相等，那么 nextval[j] = nextval[k]

- 如果不相等，则 nextval[j] = k

eg.模式串：abaabcac

4.KMP算法的程序设计

（1）为KMP算法生成next数组。

void getNext(char *t, int *next) { int j = 0, k = -1; int len = strlen(t); next[0] = -1; while (j < len - 1) { if (k == -1 || t[j] == t[k]) { j++; k++; next[j] = k; } else { k = next[k]; } } }

（2）为KMP算法生成nextval数组

void getNextval(char *t, int *nextval) { int j = 0, k = -1; int len = strlen(t); nextval[0] = -1; while (j < len - 1) { if (k == -1 || t[j] == t[k]) { j++; k++; if (t[j] != t[k]) nextval[j] = k; else nextval[j] = nextval[k]; } else { k = nextval[k]; } } }

（3）KMP算法

int KMP(char *s, char *t, int *next) { int i = 0, j = 0; int lens = strlen(s), lent = strlen(t); while (i < lens && j < lent) { if (j == -1 || s[i] == t[j]) { i++; j++; } else { j = next[j]; } } if (j >= lent) return i - j + 1; return 0; }