`
ikon
  • 浏览: 101870 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

模式匹配算法详解:KMP算法 .

    博客分类:
  • j2se
 
阅读更多

基本的模式匹配算法

假设现在有主串S=s1,...,sn,,模式串P=p1,...,pm,基本的模式匹配算法是将P中的字符p1与S中的字符s1比较,如果相等,则依次递增比较pi+1和sj+1。如果不相等,则将p1与S中的字符s2比较,依次类推。如果存i=m,则存在匹配模式,否则匹配失败。

 

KMP算法

KMP算法是由由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,所以人们称它为克努特—莫里斯—普拉特算法,该算法的时间复杂度为O(n+m),n为主串的长度,m为模式串的长度。

KMP算法的特点是不需要回潮对主串的匹配,核心思想是如果模式串当前字符a与主串当前的字符b不匹配,分两种情况,如果对于模式串中字符c之前的一个子串s,存在一个以模式串首位开始与子串s相同的子串s',则对于之前子串s其实已经通过其之后子串s'完成匹配了,所以不再需要比较,则从模式串的中间位置开始比较。如果不存在这样的子串s',则说明字符b之前开始的子串都不与模式串匹配。

算法思路:该算法的关键是当不匹配时,下一次比较将模式串的第几位开始。根据前面的分析,该位置与模式串相关,由于和主串的比较还是依次从头至尾 的,模式串重新比较的位置与主串无关,这就意味着模式串不变时,模式串中下一个匹配的位置是确定的,而不受主串影响。

对于模式串P=p1,...,pi-1,pi,...,pm如果模式串的子串p1,...,pi-1,已经和主串S=s1,...,sn中子串sj,...,sj+i-1匹配成功,而pi与sj+i不相等,即不匹配,则我们要使得j=j+1,即将模式串与主串中当前位置的下一个位置的字符串起开始比较。正如前文所说的,我们不是重新从模式串的首位开始比较,而跳跃地从一个中间位置开始比较。我们用一个长度为m的数组next[m]保存模式串中当每一个位置的字符匹配失败后,下一次模式串重新开始比较的位置。

next的值事实上是针对当模式串P中第j位的字符P[j]与主串匹配失败时计算的,分为三种情况:

第一种,next[i] = -1,当i=0时;

第二种next[i] = max{k|1<k<i且p[0],...,p[k-1]=[i-k],...p[i-1]};

其他情况,next[i] = 0

这该算法的JAVA源码如下:

 

  1. /** 
  2.  *  
  3.  * @author newstar 
  4.  * @since 2011-09-27 
  5.  * 
  6.  */  
  7. public class KMP1 {  
  8.   
  9.       
  10.     public int match(String p,String t){  
  11.         String pattern = p;  
  12.         String text = t;  
  13.         int i = 0, j = 0;  
  14.         int[] next = calculate_next(pattern);  
  15.         while(i < pattern.length()&& j <text.length()){  
  16.             if(i==-1|| pattern.charAt(i)==text.charAt(j)){  
  17.                 ++i;  
  18.                 ++j;  
  19.             }  
  20.             else{  
  21.                 i = next[i];  
  22.             }  
  23.         }  
  24.         if(j > pattern.length())   
  25.             return j-pattern.length();  
  26.         else return 0;  
  27.     }  
  28.       
  29.     public int[] calculate_next(String pattern){  
  30.         int m = pattern.length();  
  31.         System.out.println(m);  
  32.         int[] next = new int[m];  
  33.         int i = 0,j = -1;  
  34.         next[0] = -1;  
  35.         while(i<m-1){  
  36.             if(j==-1||pattern.charAt(i)==pattern.charAt(j)){  
  37.                 ++i;  
  38.                 ++j;  
  39.                 next[i] = j;  
  40.             }  
  41.             else{  
  42.                 j = next[j];  
  43.             }  
  44.         }  
  45.         return next;  
  46.     }  
  47.   
  48.     /** 
  49.      * @param args 
  50.      */  
  51.     public static void main(String[] args) {  
  52.         // TODO Auto-generated method stub   
  53.         String pattern = "abcfdabceg";  
  54.         String text = "egaradfaababcfdabcegeabcbcae";  
  55.         KMP1 run = new KMP1();  
  56.         int position = run.match(pattern,text);  
  57.         System.out.println(position);  
  58.   
  59.     }  
  60. }  

 

 

细心的读者也许会发现calculate_next函数和match函数十分类似,其实对于next的计算其实已经将模式串即当作主串又当作模式串来计算的。因为KMP算法本质其实是考虑到模式串中有相同子串,前面的子串和后面的子串相同,如果后面的子串已经是匹配成功的时,前面的子串必定和相应的主串是相匹配的。

仔细分析以下发现其实next值的计算还有改时,可以减少对主串的比较,改进后的next值的计算,分为三种情况:

第一种,如果这p[i]=p[0],则next[i]=-1。表明模式串的当前位置与模式串的首位相同,当模式串当前位置与主串的当前位匹配失败时,则模式串的首位与主串的当前位也会匹配失败,则模式串的首位应和主串当前位的下一位比较,即主串当前位向右移一位。模式串当前位为首位。

第二种,如果第一种情况不满足时,当p[0],...,p[k-]=p[i-k],...p[i],k>=0,则next[i] = 0。表明如果模式串当前位置为结束位的一个子串与模式串的首位开始的一个子串相等,如果模式串当前位置匹配失败,则表明模式串首位开始的那个子串也会匹配失败,则应从模式串的首位重新开始匹配。

第三种,如果前两情况不满足时,当p[0],...,p[k-1]=[i-k],...p[i-1]且p[k]!=p[i],k>=1,则next[i] =k-1。表明如果模式串当前位置之前的一个子串与模式串的首位开始的一个子串相等,如果模式串当前位置匹配失败,但是模式串匹配失败位置之前子串是匹配成功的,且与模式串首位开始的子串是匹配的,所以应相应从模式串的首位开始的子串的结束位开始匹配。

以下改进后的KMP算法的Java源码:

  1. /** 
  2.  *  
  3.  * @author newstar 
  4.  * @since 2011-09-27 
  5.  * 
  6.  */  
  7. public class KMP2 {  
  8.   
  9.       
  10.     public int match(String p,String t){  
  11.         String pattern = p;  
  12.         String text = t;  
  13.         int i = 0, j = 0;  
  14.         int[] next = calculate_next(pattern);  
  15.         while(i < pattern.length()&& j <text.length()){  
  16.             if(i==-1|| pattern.charAt(i)==text.charAt(j)){  
  17.                 ++i;  
  18.                 ++j;  
  19.             }  
  20.             else{  
  21.                 i = next[i];  
  22.             }  
  23.         }  
  24.         if(j > pattern.length())   
  25.             return j-pattern.length();  
  26.         else return 0;  
  27.     }  
  28.       
  29.     public int[] calculate_next(String pattern){  
  30.         int m = pattern.length();  
  31.         int[] next = new int[m];  
  32.         next[0] = -1;//next[i]=-1时表示主串当前位的下一位与模式串的第0位(首位)进行比较,   
  33.         //即表示主串的当前位置应加1,模式串的当前位置应为首位(第0位)   
  34.         System.out.println("i="+0+" "+"-1");  
  35.         int i = 1,j = 0;  
  36.         while(i<m){  
  37.             if(pattern.charAt(i)==pattern.charAt(0)){//j=0,第二种情况   
  38.                 next[i] = -1;  
  39.                 System.out.println("i="+i+" "+next[i]);  
  40.                 i++;  
  41.                 j++;  
  42.             }  
  43.             else if(pattern.charAt(i)!=pattern.charAt(j)){  
  44.                 next[i] = j;  
  45.                 System.out.println("i="+i+" "+next[i]);  
  46.                 i++;  
  47.                 j = 0;  
  48.             }  
  49.             else {  
  50.                 if(pattern.charAt(i)==pattern.charAt(j)){  
  51.                     i++;  
  52.                     j++;  
  53.                 }  
  54.                 next[i] = 0;  
  55.                 System.out.println("i="+i+" "+next[i]);  
  56.             }  
  57.         }  
  58.         return next;  
  59.     }  
  60.   
  61.     /** 
  62.      * @param args 
  63.      */  
  64.     public static void main(String[] args) {  
  65.         // TODO Auto-generated method stub   
  66.         String pattern = "abcfdabceg";  
  67.         String text = "egaababcfdabcegeabcbcae";  
  68.         KMP2 run = new KMP2();  
  69.         int position = run.match(pattern,text);  
  70.         System.out.println(position);  
  71.     }  
  72. }  
分享到:
评论

相关推荐

    模式匹配的KMP算法详解.

    模式匹配的KMP算法详解 模式匹配的KMP算法详解

    模式匹配 经典算法详解

    模式匹配算法包括AC自动解 多模式匹配算法和KMP单模式匹配算法详解

    KMP 字符串模式匹配详解

    KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的基本思路是在不回溯主串的...

    字符串模式匹配KMP算法详解.doc

    我以前一直理解不上去KMP算法(说心里话,我有点笨),当我看到这篇文章时,我理解了,这篇文章不错,说得挺细的,而且还免费,下了看看

    模式匹配KMP算法

    《数据结构》串章节字符串的模式匹配KMP算法详解

    深入串的模式匹配算法(普通算法和KMP算法)的详解

    算法的时间复杂度为O(m*n),算法如下: 代码如下://朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替{ ...

    KMP字符串模式匹配详解.doc

    KMP字符串模式匹配详解.doc,希望对在学数据结构与算法或对之感兴趣的人有所帮助!

    模式匹配的KMP算法详解

    能够帮助我们轻松彻底的解决KMP算法的问题

    kmp算法概述、原理及应用详解.pdf

    KMP算法是一种高效的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。这种算法主要用于解决字符串匹配问题,即从主字符串(text)中搜索一...

    java 中模式匹配算法-KMP算法实例详解

    主要介绍了java 中模式匹配算法-KMP算法实例详解的相关资料,需要的朋友可以参考下

    KMP字符串模式匹配详解及程序

    这是数据结构中的经典算法——KMP字符串模式匹配的详解,并且有相关的程序,保证受益匪浅。

    c/c++程序之_KMP字符串模式匹配详解

    KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。先来看一个简单匹配算法的函数:此算法的思想是...

    kmp算法详解

    KMP字符串模式匹配详解,KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法

    KMP 算法实例详解

    KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法。 分析:KMP模板题、KMP的关键是求出next的...

    KMP字符串模式匹配详解

    KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法

    详解小白之KMP算法及python实现

    在看子串匹配问题的时候,书上的关于KMP的算法的介绍总是理解不了。看了一遍代码总是很快的忘掉,后来决定好好分解一下KMP算法,算是给自己加深印象。感兴趣的朋友跟随小编一起看看吧

    字符串的模式匹配详解–BF算法与KMP算法

     BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较...

    字符串的模式匹配详解--BF算法与KMP算法

    记录一下串里面的模式匹配,模式匹配,顾名思义就是给定一个被匹配的字符串,然后用一个字符串模式(模型)去匹配上面说的字符串,看后者是否在前者里面出现。常用的有2种算法可以实现,下面我们来具体探讨下

Global site tag (gtag.js) - Google Analytics