在朴素的模式匹配算法中,主串的pos值(i)是不断地回溯来完成的(见字符串的基本操作中的Index函数)。而计算机的大仙们发现这种回溯其实可以是不需要的。既然i值不回溯,也就是不可以变小,那么考虑的变化就是子串的pos值(j)了。通过分析发现子串中如果有相等字符,j值的变化就会不相同,也就是说,这个j值的变化跟主串其实没什么关系,关键就取决于子串的结构中是否有重复的问题。
我们把子串各个位置的j值变化定义为一个数组next,那么next的长度就是子串的长度(next[0]空置)。于是可以得到下面的函数定义。
下面摘录一段阮一峰所写关于kmp的文章,增进理解:
因为空格与C 不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABC"为例,
- "A"的前缀和后缀都为空集,共有元素的长度为0;
- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
示例代码:(改编自《大话数据结构》)
#include<iostream>
using namespace std;
#define MAXSIZE 30
typedef char String[MAXSIZE + 1]; //以'\0'结尾
/* 生成一个串*/
bool StrAssign(String Dest, char *ptr)
{
cout << "Assign Str ..." << endl;
int i;
for (i = 0; ptr[i] != '\0' && i < MAXSIZE; i++)
Dest[i] = ptr[i];
Dest[i] = '\0';
return true;
}
int StrLength(String Src)
{
int i = 0;
while (Src[i] != '\0')
i++;
return i;
}
void StrPrint(String Src)
{
cout << "Print Str ..." << endl;
for (int i = 0; Src[i] != '\0'; i++)
cout << Src[i];
cout << endl;
}
/* 通过计算返回子串Sub的next数组。 */
void GetNext(String Sub, int *next)
{
int i = 1;
int j = 0;
next[1] = 0;
while (i < StrLength(Sub))
{
if(j == 0 || Sub[i - 1] == Sub[j - 1])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];/* 若字符不相同,则j值回溯 */
}
}
void GetNextVal(String Sub, int *nextval)
{
int i = 1;
int j = 0;
nextval[1] = 0;
while (i < StrLength(Sub))
{
if(j == 0 || Sub[i - 1] == Sub[j - 1])
{
++i;
++j;
if (Sub[i - 1] != Sub[j - 1]) /* 若当前字符与前缀字符不同 */
nextval[i] = j;/* 则当前的j为nextval在i位置的值 */
else
nextval[i] = nextval[j];/* 如果与前缀字符相同,则将前缀字符的 */
/* nextval值赋值给nextval在i位置的值 */
}
else
j = nextval[j];
}
}
/* 返回子串Sub在主串Src中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
int IndexKMP(String Src, String Sub, int pos)
{
cout << "KMP Index ..." << endl;
int i = pos - 1;
int j = 0;
int next[10];
int len1 = StrLength(Src);
int len2 = StrLength(Sub);
/*GetNext(Sub, next);*/
GetNextVal(Sub, next);
while (i < len1 && j < len2)
{
/* 两字母相等则继续,与朴素算法增加了j=0判断 */
if (j == 0 || Src[i -1] == Sub[j -
1])
{
++i;
++j;
}
else
{
j = next[j];/* j退回合适的位置,i值不变 */
}
}
if (j == len2)
return i - len2 + 1;
else
return 0;
}
int main(void)
{
String Str1, Str2, Str3, Str4;
StrAssign(Str1, "defewabcabxwfew");
StrAssign(Str2, "abcabx");
StrAssign(Str3, "ababaaaba");
StrAssign(Str4, "htrhdhsgtrhababaaabafwrew");
int next[10]; //next[0]空置
GetNext(Str2, next);
cout << "Get Next array ..," << endl;
for (int i = 1; i < 7; i++)
cout << next[i];
cout << endl;
GetNext(Str3, next);
cout << "Get Next array ..," << endl;
for (int i = 1; i < 10; i++)
cout << next[i];
cout << endl;
GetNextVal(Str3, next);
cout << "Get NextVal array ..," << endl;
for (int i = 1; i < 10; i++)
cout << next[i];
cout << endl << endl;
cout << IndexKMP(Str1, Str2, 1) << endl;
cout << IndexKMP(Str4, Str3, 1) << endl;
return 0;
}
输出为: