一个效率非常高的字符串匹配算法
【基本思想】
利用部分匹配表比较字符串S是否包含字符串P
【步骤】
算出一张《部分匹配表》（Partial Match Table）--P
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。
"前缀"指除了最后一个字符以外，一个字符串的全部头部组合
"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
1. 部分匹配表
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
| A | AB | ABC | ABCD | ABCDA | ABCDAB | ABCDACD |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 2 | 0 |
2. next 数组
next 数组考虑的是除当前字符外的最长相同前缀后缀。
计算某个字符对应的 next 值，就是看这个字符之前的字符串中有多大长度的相同前缀后缀，使其向右移动一位，然后初始值赋为 -1。
| A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|
| A | B | C | D | A | B | D |
| -1 | 0 | 0 | 0 | 0 | 1 | 2 |
3. 遍历比较
假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
- 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
- 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。
- 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。
【实例分析】
S[10] 跟 P[6] 匹配失败。j = next[j]，即 j 从 6 变到 2（字符 D 对应部分匹配表的值为0，对应的 next 值为 2）
C 处再度失配
j = next[j] = 0
A 与空格失配，j = next[j] = -1。
i++,j++
【伪代码】
假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
* 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
* 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。
【代码实现】
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
【性能分析】
O(n+m)
网友评论