算法研究：字符串的KMP模式匹配

算法研究：字符串的KMP模式匹配2013-08-26 csdn Simba888888在朴素的模式匹配算法中，主串的pos值（i）是不断地回溯来完成的（见字符串的基本操作中的Index函数）。而计算机的大仙们发现这种回溯其实可以是不需要的。既然i值不回溯，也就是不可以变小，那么考虑的变化就是子串的pos值（j）了。通过分析发现子串中如果有相等字符，j值的变化就会不相同，也就是说，这个j值的变化跟主串其实没什么关系，关键就取决于子串的结构中是否有重复的问题。

我们把子串各个位置的j值变化定义为一个数组next,那么next的长度就是子串的长度（next[0]空置）。于是可以得到下面的函数定义。

示例代码：（改编自《大话数据结构》）

#include<iostream>using namespace std;#define MAXSIZE 30typedef char String[MAXSIZE + 1]; //以""结尾/* 生成一个串*/bool StrAssign（String Dest, char *ptr）{cout << "Assign Str ..." << endl;int i;for （i = 0; ptr[i] ！= "" && i < MAXSIZE; i++）Dest[i] = ptr[i];Dest[i] = "";return true;}int StrLength（String Src）{int i = 0;while （Src[i] ！= ""）i++;return i;}void StrPrint（String Src）{cout << "Print Str ..." << endl;for （int i = 0; Src[i] ！= ""; 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;}elsej = 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位置的值 */elsenextval[i] = nextval[j];/* 如果与前缀字符相同，则将前缀字符的 *//* nextval值赋值给nextval在i位置的值 */}elsej = 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;elsereturn 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;}

输出为：