转自: http://blog.csdn.net/WINCOL/article/details/4795369
KMP 的思想是这样的:
利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离,换言之,问题由模式串决定,不是由目标决定!
比如
模式串ababac 这个时候我们发现在c 处不匹配,然后我们看c 前面那串字符串的最大相等前后缀,然后再来移动
下面的两个都是模式串,没有写出来匹配串
原始位置 ababa c
移动之后 aba bac
因为后缀是已经匹配了的,而前缀和后缀是相等的,所以直接把前缀移动到原来后缀处,再从原来的c 处,也就是现在的第二个b 处进行比较。 这就是KMP
//求模式串T的next函数,修正值并填入next数组 void getNext(string T, int next[]) { int i = 1, j = 0; next[1] = 0; while (i < T[0]) //T[0]表示串T的长度 { if (j == 0 || T[i] == T[j])//T[i]表示后缀的单个字符 { //T[j]表示前缀的单个字符 ++i; ++j; if(T[i]!=T[j]) //若当前字符与前缀字符不同 next[i] = j; //则当前的j为next在i位置的值 else next[i] = next[j]; //若与前缀字符相同,则将前缀 //字符的next值赋值给next在i位置的值 } else { j = next[j]; //字符不相同,则j值回溯 } } } //返回子串T在主串S中posi之后的位置。若不存在,返回值为0 //T非空,1<=posi<StrLength(S) int kmp(string S, string T, int posi) { int i = posi; //i用于主串S当前位置下标值,若posi不为0 //则从posi位置开始匹配 int j = 1; //j用于子串T中当前位置下标值 int next[255] = GetNext(T, next); //当i小于S的长度,j小于T的长度,就一直循环 while(i <= S[0] && j <= T[0]) { if (j == 0 || S[i] == T[j])//两字符相等就继续 { ++i; ++j; } else //指针后退,重新开始匹配 { j = next[j]; //j返回合适的位置,i的值不变 } } if(j > T[0]) return i - T[0]; else return 0; }
相关推荐
KMP算法
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
kmp算法,数据结构的实验报告,大学实验报告,希望能帮到大家
数据结构中KMP算法过程的Flash演示
kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的...
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
kmp算法的原理以及kmp算法的源代码
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
利用KMP算法进行子串的快速查找,能够达到较高的速率