重温数据结构-串(KMP) 2018-08-04 感觉串的操作挺无聊的。主要看了“一”下KMP,嗯,一下 ~ KMP算法课本伪代码1234567891011121314151617181920212223242526272829303132333435363738394041int Index_KMP(SString S, SString T, int pos){ //利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法 //其中,T非空,1<<pos<<StrLength(S) i = pos; j = 1; 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;}void get_next(SString T, int next[]){ // 求模式串T的next函数值并存入next数组 i= 1; next[1] = 0; j = 0; while(i < T[0]) { if(j == 0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; }} 完整KMP的C Plus的实现:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<iostream>#include<cstring>#include<stdlib.h>using namespace std;void findnext(char *pattern, int *next) { int len = strlen(pattern); next[0] = 0; for(int i = 1; i < len; i++) { int j = next[i-1]; while(j > 0 && pattern[j] != pattern[i]) j = next[j-1]; if(pattern[j] == pattern[i]) next[i] = j + 1; else next[i] = 0; } cout << "partial match table: "; for(int i = 0; i < len; i++) cout << next[i] << " ";}int KMP(char *pattern, char *sourceString, int *next) { int sourcelength = strlen(sourceString); int patternlength = strlen(pattern); int p = 0, s = 0; while(p < patternlength && s < sourcelength && patternlength <= sourcelength) { if(pattern[p] == sourceString[s]) { s++; p++; } else { if(p == 0) s++; else p = next[p - 1]; } } return p == patternlength ? s - patternlength : -1;}int main() { int next[100]; char pattern[100]; char sourceString[100]; int position; cout << "please input source string and pattren:" << endl; while(cin >> sourceString >> pattern) { findnext(pattern, next); position = KMP(pattern, sourceString, next); cout << endl << "matched from " << position << " to " << position + strlen(pattern) <<endl; } system("pause");} 赏 谢谢你请Leo吃糖果哦 支付宝 微信 数据结构与算法 扫一扫,分享到微信