正文 

当前位置： 首页 > java > java教程

kmp及其改进算法

我是修电脑的 我是修电脑的     2022-09-04     396

关键词：

本文主要讲述KMP已经KMP的一种改进方法。若发现不正确的地方，欢迎交流指出，谢谢！


KMP算法的基本思想:

 

KMP的算法流程:

每当一趟匹配过程中出现字符比较不等时，不需回溯 i 指针，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。

设S为目标串，T为模式串，设 i 指针和 j 指针分别指示目标串和模式串中正待比较的字符。

开始时，令i=0，j=0。如果Si==Tj，则使i和j的值分别增加l；反之，i不变，j的值退回到j=next[j]的位置(即模式串右滑)，然后再对Si和Tj进行比较。依次类推，直到出现下列两种情况之一：

1．j值退回到某个j=next[j]时，有Si==Tj，则指针的值各增加1后，再继续匹配；

2．j值退回到 j=-1，此时令指针的值各增加1，也即下一次对Si+1和T0进行比较。

模式匹配KMP算法的时间复杂度为O(m+n)，只有当模式与珠串之间存在许多“部分匹配”的情况下显得比朴素字符匹配算法快得多。但是KMP算法最大的特点就是指示主串的指针不需要回溯，整个过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。


 

跟朴素匹配算法的主要差异：

   在于当Si != Tj的时候，朴素算法采用的是将Tj往前推一格，然后将j置为0，重新进行匹配，而KMP采用的方法是将j置为next[j]，然后再匹配。

很显然，这里的next[j]是算法的核心。


 

下面是next[j]的计算方法，以及代码的实现：

[cpp] view plaincopy
 
 
  1. void get_nextval( const char *s, int *nextval)  
  2. {  
  3.      int len = strlen(s);      
  4.      int i = 0, j = -1;  
  5.   
  6.      nextval[0] = -1;      
  7.   
  8.      while( i < len-1 ){  
  9.           if( j == -1 || s[i] == s[j] ){  
  10.                ++i;      
  11.                ++j;      
  12.   
  13.                if( s[i] != s[j] ){  
  14.                     nextval[i] = j;      
  15.                }else{  
  16.                     nextval[i] = nextval[j];      
  17.                }  
  18.           }else{  
  19.                j = nextval[j];      
  20.           }  
  21.      }  
  22.   
  23.      return ;      
  24. }  


 

得到了next[j]之后，KMP算法的实现就很简单了，按照上面KMP的算法流程，可以很快写出代码：

[cpp] view plaincopy
 
 
  1. //s为匹配串  
  2. //t为主串  
  3. int kmp( const char *s, const char *t )  
  4. {  
  5.      int k = -1;      
  6.      int nextval[N] = {0};      
  7.      int s_len = strlen(s);      
  8.      int t_len = strlen(t);      
  9.   
  10.      get_nextval( s, nextval );     //get_nextval[]  
  11.      cout<<"nextval:"<<endl;      
  12.      for( k = 0; k < s_len; k++)  
  13.           cout<<nextval[k]<<" ";      
  14.      cout<<endl;      
  15.   
  16.      int i = 0, j = 0;      
  17.       
  18.   
  19.      while( i < t_len && j < s_len ){  
  20.           if( j == -1 || t[i] == s[j] ){  
  21.                i++;      
  22.                j++;      
  23.           }else{  
  24.                j = nextval[j];      
  25.           }  
  26.      }  
  27.   
  28.   
  29.      if( j >= s_len ){  
  30.           return i-s_len;      
  31.      }else{  
  32.           return -1;      
  33.      }  
  34. }  


 

下面给出一个KMP的实现及测试代码：

[cpp] view plaincopy
 
 
  1. #include <iostream>  
  2. using namespace std;      
  3. #define N 100  
  4.   
  5. void get_nextval( const char *s, int *nextval);      
  6. int kmp( const char *s, const char *t );      
  7.   
  8.   
  9. //s为匹配串  
  10. //t为主串  
  11. int kmp( const char *s, const char *t )  
  12. {  
  13.      int k = -1;      
  14.      int nextval[N] = {0};      
  15.      int s_len = strlen(s);      
  16.      int t_len = strlen(t);      
  17.   
  18.      get_nextval( s, nextval );     //get_nextval[]  
  19.      cout<<"nextval:"<<endl;      
  20.      for( k = 0; k < s_len; k++)  
  21.           cout<<nextval[k]<<" ";      
  22.      cout<<endl;      
  23.   
  24.      int i = 0, j = 0;      
  25.       
  26.   
  27.      while( i < t_len && j < s_len ){  
  28.           if( j == -1 || t[i] == s[j] ){  
  29.                i++;      
  30.                j++;      
  31.           }else{  
  32.                j = nextval[j];      
  33.           }  
  34.      }  
  35.   
  36.   
  37.      if( j >= s_len ){  
  38.           return i-s_len;      
  39.      }else{  
  40.           return -1;      
  41.      }  
  42. }  
  43.   
  44. void get_nextval( const char *s, int *nextval)  
  45. {  
  46.      int len = strlen(s);      
  47.      int i = 0, j = -1;  
  48.   
  49.      nextval[0] = -1;      
  50.   
  51.      while( i < len-1 ){  
  52.           if( j == -1 || s[i] == s[j] ){  
  53.                ++i;      
  54.                ++j;      
  55.   
  56.                if( s[i] != s[j] ){  
  57.                     nextval[i] = j;      
  58.                }else{  
  59.                     nextval[i] = nextval[j];      
  60.                }  
  61.           }else{  
  62.                j = nextval[j];      
  63.           }  
  64.      }  
  65.   
  66.      return ;      
  67. }  
  68.   
  69. int main()  
  70. {  
  71.      char s[N], t[N];      
  72.      while( cin>>s >>t ){  
  73.           int i = 0;      
  74.           i = kmp( s, t );      
  75.   
  76.           cout <<"ans = " <<i <<endl;      
  77.      }  
  78.      return 0;      
  79. }  



测试如下：

技术分享

KMP模式匹配问题的改进思想和方法

KMP的不足之处：

    通过观察，我们可以在原有的KMP算法中，发现一个不足的地方，也就是我们将要改进的地方就是，因为，子串的出现是随机的，如果子串在主串出现的位置靠后的时候，KMP算法实在显得比较低效。现在我们给出一个例子来说明问题。

 

主串为：aspowqeursoolksnkhiozbgwoinpweuirabaac

子串为：abaac

 

    容易看出，子串要到最后才会得到匹配，因此，我们提出我们的思想——从主串的首和尾同时进行匹配，那样，就可以提高算法的效率，并且，除了在这个方面提高算法效率以外，我们还想到，当 m >>n，，n>>0的时候(m为主串长度，n为子串长度)，并且子串并没有在主串中出现的话，那么，在改进算法中，我们将不需要比较到最末才判断是否存在匹配的子串，而是通过剩下的字符数，来判断是否存在足够的字符与子串匹配，如果不足的话，那样就不存在，否则就继续匹配下去。


 

如何实现从主串末尾想串头开始匹配呢?

    我们这里有两个方案：第一个方案是，把子串逆转，然后沿用旧的KMP算法中的next函数求出其逆转后的子串的next值，再用以进行匹配；第二个方案就是，不需要把子串逆转，而是采用一个新的next函数直接求出其逆转后的next值。

    第一二个方案比较后，我们选择第二个方案。因为，在 n>>0的时候，明显地，在把子串逆转的时候同时需要多一个字符串来存放，并且，在不同的匹配都需要一个新的字符串，这样就大大地浪费空间了,除此之外，第一个方案至少要做遍历子串两次，而第二个方案只需要遍历子串一次就可以了。所以我们决定采用构建一个新的next函数来求出其逆转后的子串next值。

    我们新的next函数的思想就是，把末字符看成是首字符，然后，仿照KMP算法中的next函数的实现方式最终实现的。现在，我们给出实现的新的next函数：

[cpp] view plaincopy
 
 
  1. void nextres( char* p, int *next, int n )  
  2. {  
  3.         int i, j, k;      
  4.         i = n-1, j = -1;          
  5.         *next = -1;       
  6.         k = n;    
  7.         while( i > 0 ){  
  8.                 if( j == -1 || *(p+i) == *(p+k-j-1)){  
  9.                         i--, j++;         
  10.                         if( *(p+i) != *(p+k-j-1) )  
  11.                                 *(next+n-i-1) = j;        
  12.                         else  
  13.                                 *(next+n-i-1) = *(next+j);        
  14.                 }  
  15.                 else   
  16.                         j = *(next+j);    
  17.         }  
  18.   
  19. }  



在得到逆转后的子串的next函数后，我们就可以进行串的匹配了。其基本思路同原KMP算法，下面我们就给出匹配过程的实现：

[cpp] view plaincopy
 
 
  1. int march( char* mainhead, char* head, int mainlen, int lenth, int *next1, int *next2 )  
  2. {  
  3.         int i, j, k, l, m;        
  4.         i = 0, j = 0, k = mainlen-1, m = lenth-1, l = 0;          
  5.         while( (m>0 && j<lenth) || lenth == 1 ){  
  6.                 if( lenth == 1 && ( *(mainhead+i) == *(head+j) ||  
  7.                         *(mainhead+k) == *(head+m)))  
  8.                         return 1;         
  9.                 if( j == -1 || *(mainhead+i) == *(head+j))  
  10.                         i++, j++;         
  11.                 else  
  12.                         j = *(next1+j);   
  13.                 if( l == -1 || *(mainhead+k) == *(head+m)){  
  14.                         k--;  
  15.                         l++;  
  16.                         m = lenth==2?m-l:m-1;     
  17.                 }else{  
  18.                         l = *(next2+1);   
  19.                         if( l != -1 )  
  20.                                 m = m-l;          
  21.                         else  
  22.                                 m = lenth-1;      
  23.                 }  
  24.                 if( k-i < m-j )  
  25.                         return 0;         
  26.         }  
  27.   
  28.         if( m <= 0 || j >= lenth)  
  29.                 return 1;         
  30.         else   
  31.                 return 0;         
  32. }  



新的KMP算法在某种程度上的确可以提高模式匹配的效率。除此以外，新的模式匹配算法还能提早结束不必要的匹配。

 

from: http://blog.csdn.NET/cyh_24/article/details/8162436

 
顶
0
踩












图解kmp算法原理及其代码分析(代码片段)

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。该算法是字符串两大难点算法之一。在这里我想对提出该算法的三位... 查看详情

改进kmp模式匹配算法(代码片段)

看了算法的大致步骤，然后自己一一证明了每一步的正确性，注释里写了一些理解。这也不是新鲜的做法，只是感觉这个程序非常精巧，反复地使用数学归纳法。让我感觉很新鲜。1/*2next[i]存放：match[i]处失配,orig在对应位置将要... 查看详情

改进的kmp算法的执行过程

比如有模式串 t="aaaabaac" 首先我们至少光看的话，发现未修正的next数组是很好列出来的是next:0,1,2,3,4,1,2,3在这个基础上我们可以很容易的写出修正好的nextVal数组：设nextVal[1]=0;(1)i=2,看next[i]=next[2]=1=j,因为t[i]==t[j]即t[2]==t[1],... 查看详情

kmp算法中改进的nextval数组

我们在上篇文章中讲到的NEXT数组其实再某些情况下是有缺陷的，例如在模式串s=’aaaab’和主串t=’aaabaaaab’匹配时，当在i=4,j=4时，产生失配，由下图的next数组中指出还需进行i=4,j=3;i=4,j=2;i... 查看详情

kmp算法

KMP算法KMP算法的简介　　KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，简称KMP算法。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现... 查看详情

数据结构kmp算法配图详解（超详细）(代码片段)

...MP算法的具体实现五、KMP算法的时间复杂度六、next数组的改进--nextval数组及具体代码七、最后的话一、什么是KMP算法？KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V 查看详情

深入理解伙伴算法及其改进

    今天遇到很好的一个腾讯面试官，进一步探讨了伙伴算法，面试官非常nice，对伙伴算法的优缺点详细给我讲了一下，发现这个算法值得深入研究一波~看了很多资料，下面整理资料，然后谈谈自己的理解。 ... 查看详情

kmp算法小结

...博客总计一下。1.KMP算法介绍KMP算法是一种字符串搜索的改进算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模... 查看详情

kmp算法(代码片段)

KMP算法KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达... 查看详情

字符串匹配---kmp算法

...csdn.net/ebowtang/article/details/49129363前言　　　KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信... 查看详情

kmp算法

 1、概述　　KMP算法是一种改进的字符串匹配算法，关键在于利用匹配失败后的信息，尽量减少模式串与主串的次数。2、算法原理　　举个简单的例子：主串为“BBCABCDABABCDABCDABDE”，匹配串为“ABCDABD” 　　通常我们比较... 查看详情

kmp算法-理论

...现，所以去百度了一翻，做个记录。KMP算法简介：是一种改进的字符串匹配算法。核心思想：通过匹配失败后的信息，尽量减少模式串与主串的匹配次数来达到快速匹配的目的。leetcode题目：给定一个haystack字符串和一个needle字... 查看详情

kmp子串查找算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法，由他们的名字首字母组成）。KMP算法的关键是利用已经部分匹配的信息，尽量减少... 查看详情

kmp算法

KMP算法（三个人名字开头字母）对BF算法进行了改进，省去了一部分没必要的比较，提高了算法的效率。K,M,P这三个人发现了BF算法中一些模式中遗憾的用于模式匹配的信息，这种信息就是模式匹配中的“部分匹配“的信息。首先... 查看详情

kmp算法深度解析

...，希望能够有助于学习与理解。 1、KMP算法   一种改进 查看详情

[聚类算法]k-means优缺点及其改进

[聚类算法]K-means优缺点及其改进【转】：http://blog.csdn.net/u010536377/article/details/50884416K-means聚类小述大家接触的第一个聚类方法，十有八九都是K-means聚类啦。该算法十分容易理解，也很容易实现。其实几乎所有的机器学习和数据... 查看详情

kmp~(代码片段)

...t，搞得朱洪dalao的优化打不了。（题外话）KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信... 查看详情

❤️详解kmp算法(代码片段)

...题，带你彻底了解KMP的原理以及实现。KMP算法是一种改进的字符串匹配算法，KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next数组实现ÿ... 查看详情