KMP算法,在《数据结构》课上听过,似是非懂,读完大学后全忘光了。Brute-Force算法,简单,谁都知道。从主串S的第pos个字符起与模式串进行比较,匹配不成功时,从主串S的第pos+1个字符重新与模式串进行比较。如果主串S的长度是n,模式串长度是m,那么Brute-Force的时间复杂度是o(m*n)。最坏情况出现在模式串的子串频繁出现在主串S中。虽然它的时间复杂度为o(m*n),但在一般情况下匹配时间为o(m+n),因此在实际中它被大量使用。
前几日,重新拾起了KMP算法,然后向MM讲解之。KMP的主要思想是:每当一趟匹配过程中出现字符比较不等时,不需回溯主串S的指针,而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离后,继续进行比较。
模式串到底向右滑动多少,在KMP算法中是用一个数组来存储的。针对模式串中的每个索引j,都将有一个对应的值。此值的含义为模式串中位置从0到j-1构成的串中所出现的首尾相同的子串的最大长度加1。
下面给出具体实现:
/*
* n is the length of text,while m is the length of pattern.
* And pos which is zero-indexed is the start point of search.
*/
int kmp(char* text,int n,char *pattern,int m,int pos){
int i,j;
//Generate the array of next
int* next = (int*)malloc(m*sizeof(int));
i = 0;
j = -1;
next[i] = j;
while(i<m){
if((j==-1) || (pattern[i]==pattern[j])){
i++;
j++;
if(pattern[i]!=pattern[j])
next[i] = j;
else
next[i] = next[j];
}else{
j = next[j];
}
}
int k = 0;
for(k=0;k<m;k++)
printf("next:%d\n",next[k]);
//Search
i = pos;
j = 0;
while(i<n&&j<m){
if((j==-1) || (text[i]==pattern[j])){
i++;
j++;
}else{
j = next[j];
}
}
if(j==m)
return i-m;
else
return 0;
}
KMP算法的时间开销包括两部分,一个是求next数组元素的值,此时的时间开销是o(m);一个是搜索,此时的时间开销是o(n)。因此,它的时间复杂度是o(m+n)
分享到:
相关推荐
让你迅速透彻的理解KMP算法! [1] http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm [KMP 77]D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of ...
KMP算法(Knuth-Morris-Pratt Algorithm)是一种改进的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,以达到快速匹配的目的...
KMP算法,全称Knuth-Morris-Pratt算法,是一种用于在一个主文本字符串(text)中查找一个模式字符串(pattern)的子串的高效算法。KMP算法的核心思想是利用模式字符串的特点,在匹配过程中尽可能地减少重复的字符...
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...
KMP 算法,即 Knuth-Morris-Pratt 算法,是一种用于字符串匹配的经典算法。与朴素的字符串匹配算法相比,KMP 算法具有更高的效率,特别是在处理大型文本时。本文将介绍 KMP 算法的原理,并提供 C++示例代码来演示...
KMP-knuth-morris-pratt-Python 在文本中查找模式的Knuth-Morris-Pratt算法的实现
KMP(Knuth-Morris-Pratt)算法是一种改进的字符串匹配算法,用于在一个文本字符串(T)中查找一个词(W)的出现位置。KMP算法的核心在于当字符串匹配发生不一致时,能知道已经部分匹配这个有效信息,利用这个信息...
kmp算法
KMP算法的核心思想是利用已经匹配过的信息,当发生不匹配时,知道一些字符肯定不会出现在模式串的某个位置,从而利用这些信息跳过一些不必要的比较。具体来说,KMP算法通过维护一个“部分匹配表”(也称为“失败函数...
KMP algorithm for matching string problem
Knuth-Morris-Pratt 算法
KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。KMP算法由D.E.Knuth,J.H.Morris和V.R.Pratt在 Brute-Force算法的基础上提出的模式匹配的改进算法。因此人们称它为...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
克努斯-莫里斯-普拉特算法,KMP算法(Knuth–Morris–Pratt algorithm) 一种字符串查找算法。在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
公里数Javascript 中的字符串搜索算法。安装npm install kmpbower install kmp用法 var kmp = require ( 'kmp' ) ;console . log ( kmp ( 'she sells seashells by the seashore' , 'shell' ) ) ; // 13console . ...
KMP 算法(Knuth-Morris-Pratt) Rabin-Karp 算法 Boyer-Moore 算法 A* 搜索算法 Dijkstra 算法 Bellman-Ford 算法 Floyd-Warshall 算法 Kruskal 算法 Prim 算法 Edmonds-Karp 算法 Ford-Fulkerson 算法