1352 - 算法4-6：KMP字符串模式匹配算法实现
KMP算法是字符串模式匹配算法中较为高效的算法之一，其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法，同时前面的例子中也描述了子串移动位置的数组实现的算法。前面你已经实现了子串移动的数组，现在就来利用该数组来实现KMP模式匹配。
下面是相应的算法：
<!--[if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0<![endif]-->
<span style="font-size:10.5000pt;font-family:'宋体';">图：<span>KMP</span><span>算法</span></span>
Input
3组字符串，每组字符串占一行。每行包含由空格分隔的两个字符串，字符串仅由英文小写字母组成且长度不大于100。
Output
每组数据输出1行，输出后一个字符串在前一个字符串中的位置，如果不匹配，则输出0。
Examples
Input
string str thisisalongstring isa nosubstring subt
Output
1 5 0
Hint
提示：
表示字符串的数据结构依然是字符数组。
总结：
KMP算法调用很简单，但难的是理解算法的思想。掌握算法的思想才能说是掌握算法。
Solution C
#include<stdio.h> #include<string.h> #define S 10000 #define T 100 int next[T]={0}; void get_next(char t[],int next[]) { int i=0,j=-1; while(t[i+1]!='\0') { if(j==-1||t[i]==t[j]) { ++i;++j; next[i]=j+1; } else j=next[j]-1; } } void get_nextval(char t[],int next[]) { int i=0,j=-1; while(t[i+1]!='\0') { if(j==-1||t[i]==t[j]) { ++i;++j; if(t[i]!=t[j]) next[i]=j+1; else next[i]=next[j]; } else j=next[j]-1; } } int kmp(char s[],char t[],int pos) { int i=pos-1,j=0,a=strlen(s),b=strlen(t); while(i<=a-1&&j<=b-1) { if(j==-1||s[i]==t[j]) {++i;++j;} else j=next[j]-1; } if(j==b) return i-j+1; else return 0; } int main() { int i; char s[S],t[T]; for(i=1;i<=3;i++){ scanf("%s %s",s,t); //get_next(t,next); get_nextval(t,next); printf("%d\n",kmp(s,t,1));} return 0; }
Solution C++
#include <stdio.h> #include <string.h> #define MAXSTRLEN 100 typedef char SString[MAXSTRLEN+2]; void InputString(SString &str) { // 读取字符串 scanf("%s", str + 1); // 首先用scanf读取字符串 str[0] = strlen(str + 1); // 求出字符串的长度并保存在str[0]中 } void get_next(SString T, int *next) { // 算法4.7 int i = 1; next[1] = 0; int j = 0; while (i < T[0]) { if (j == 0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; } } int Index_KMP(SString S, SString T, int pos) { // 算法4.6 // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 // KMP算法。其中，T非空，1≤pos≤StrLength(S)。 int next[255]; int i = pos; int j = 1; get_next(T, next); while (i <= S[0] && j <= T[0]) { if (j == 0 || S[i] == T[j]) { // 继续比较后继字符 ++i; ++j; } else j = next[j]; // 模式串向右移动 } if (j > T[0]) return i - T[0]; // 匹配成功 else return 0; } // Index_KMP int main() { int i; SString str, sub; for (i = 0; i < 3; i++) { InputString(str); // 输入母串 InputString(sub); // 输入子串 printf("%d\n", Index_KMP(str, sub, 1)); // 输出调用 KMP 的函数结果 } return 0; }
Hint
提示：
表示字符串的数据结构依然是字符数组。
总结：
KMP算法调用很简单，但难的是理解算法的思想。掌握算法的思想才能说是掌握算法。