在朴素的模式匹配算法中,主串的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; }
输出为:
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句