当前位置:首页 > 开发 > 系统架构 > 架构 > 正文

字符串匹配之KMP算法思路、原理与Java实现

发表于: 2015-02-24   作者:chenhaodejia   来源:转载   浏览次数:
摘要: 问题描述: 判断字符串a是否包含字符串b。我们称a为文本串,b为模式串。比如 [plain]   view plain copy a = bcabcabcabbcabcabcabcabd       ||||||||||/   b = 

问题描述:

判断字符串a是否包含字符串b。我们称a为文本串,b为模式串。比如

[plain]   view plain copy
  1. a = bcabcabcabbcabcabcabcabd  
  2.     ||||||||||/  
  3. b = bcabcabcabc  

算法思路:

如上例中/处两个字符匹配失败,如果模式串右移一个字符从文本串第二个字符开始重新进行匹配,显然效率太低。

KMP算法的精髓在于当文本串和模式串发生不匹配时,利用模式串自身的特点,尽可能多的移动模式串,使之能够在文本串不匹配处继续进行匹配。

如上例,发生不匹配时,模式串可以右移三次,在目标串不匹配处继续进行:

[plain]   view plain copy
  1. a=bcabcabcabbcabcabcabcabd  
  2.      |||||||/  
  3. b=   bcabcabcabc  

算法原理:

模式串b=b1b2b3b4…bn,如果有b1b2b3b4…bk-1等于bj-(k-1)bj-(k-2)bj-(k-3)…bj-1,那么在进行匹配时,如果在j处与文本串i处匹配失败,我们可以将模式串右移j-k个字符,即直接将文本串i处字符与bk进行匹配。由于b1b2b3b4…bk-1等于bj-(k-1)bj-(k-2)bj-(k-3)…bj-1,显然模式串前k-1位的字符是与文本串i处前k-1位字符是匹配的。

所以问题转化为求模式串各字符的k值,我们记作K(j),该值可以根据模式串自身求得。

伪代码:

假设有文本串a和模式串b。index从1开始。

求K(j)的伪代码如下:

 

[plain]   view plain copy
  1. 初始化:i = 1,j = 0, K(1) = 0;  
  2. while (i < b.length) {  
  3.    if (j == 0 || b(i) = b(j)) {  
  4.        i++;  
  5.        j++;  
  6.        K(i) = j;  
  7.    } else {  
  8.        j = K(j);   
  9.    }  
  10. }  

判断匹配的伪代码如下:

 

[plain]   view plain copy
  1. 初始化:i = 1, j = 1;  
  2. while (i <= a.length && j <= b.length) {  
  3.     if (j ==0 || a(i)= b(j)) {  
  4.              i++;  
  5.              j++;  
  6.     } else {  
  7.              j = K(j);  
  8.     }  
  9. }  
  10. if (j > b.length) {  
  11.     return true;  
  12. }  
  13. return false;  

 

Java实现:

[java]   view plain copy
  1. package cn.dfeng;  
  2.   
  3. /** 
  4.  * KMP算法的实现 
  5.  * @author dfeng 
  6.  * 
  7.  */  
  8. public class KMPAlgorithm {  
  9.   
  10.     /** 
  11.      * 判断是否匹配 
  12.      * @param target 目标文本串 
  13.      * @param mode 模式串 
  14.      * @return 匹配结果 
  15.      */  
  16.     public static boolean matchString(String target, String mode) {  
  17.         //为了和算法保持一致,使index从1开始,增加一前缀  
  18.         String newTarget = "x" + target;   
  19.         String newMode = 'x' + mode;  
  20.           
  21.         int[] K = calculateK(mode);  
  22.           
  23.         int i = 1;  
  24.         int j = 1;  
  25.         while(i <= target.length() && j <= mode.length()) {  
  26.             if (j == 0 || newTarget.charAt(i) == newMode.charAt(j)) {  
  27.                 i++;  
  28.                 j++;  
  29.             } else {  
  30.                 j = K[j];  
  31.             }  
  32.         }  
  33.           
  34.         if (j > mode.length()) {  
  35.             return true;  
  36.         }  
  37.         return false;  
  38.     }  
  39.       
  40.     /* 
  41.      * 计算K值 
  42.      */  
  43.     private static int[] calculateK(String mode) {  
  44.         //为了和算法保持一致,使index从1开始,增加一前缀  
  45.         String newMode = "x" + mode;  
  46.         int[] K = new int[newMode.length()];  
  47.         int i = 1;  
  48.         K[1] = 0;  
  49.         int j = 0;  
  50.           
  51.         while(i < mode.length()) {  
  52.             if (j == 0 || newMode.charAt(i) == newMode.charAt(j)){  
  53.                 i++;  
  54.                 j++;  
  55.                 K[i] = j;  
  56.             } else {  
  57.                 j = K[j];  
  58.             }  
  59.         }  
  60.           
  61.         return K;  
  62.     }  
  63.     /** 
  64.      * @param args 
  65.      */  
  66.     public static void main(String[] args) {  
  67.         String a = "bcabcabcabbcabcabcabcab";  
  68.         String b = "bcabcabcabc";//"ababbaaba";//  
  69.         System.out.println(KMPAlgorithm.matchString(a, b));  
  70.   
  71.     }  
  72.   
  73. }  

字符串匹配之KMP算法思路、原理与Java实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1 // KMP.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include <iostr
字符串面试题系列之七:字符串全排列 编译环境 本系列文章所提供的算法均在以下环境下编译通过。 【
字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽 本文内容框架: §1 Boyer-M
字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽 转载自:http://dsqiu.itey
处理字符串的过程中,难免会遇到字符匹配的问题。常用的字符匹配方法 1. 朴素模式匹配算法(Brute-Fo
字符串匹配 -- KMP算法 参考资料 1 数据结构( C 语言版) 2 Matrix67 : KMP算法详解 3 任我行 :KMP
KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.
当两个字符串进行顺序匹配出现某字符匹配不正确时,被匹配字串的开始位置要回退,这是个不效率的工
KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.
   字符串匹配是计算机的基本任务之一。   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号