字符串KMP算法

发表于   |   分类于   |  

　　之前学习一些数据结构教材上的kmp算法觉得讲的很复杂，要看很久才能明白，最近看了这篇文章觉得对理解kmp算法很有帮助：http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/ 下面把自己的理解记录一下

　　kmp算法是用来解决子串匹配问题的，也就是输入是一个原字符串txt和一个模式串pat，输出的是所有txt中子串匹配pat的所有位置。我们知道用暴力的算法进行子串匹配复杂度是O(m*(n-m+1))，n是原字符串的长度，m是模式串的长度，而且保证n>m。但是kmp算法复杂度是O(n)。kmp算法需要借助一个辅助数组lps[]，大小是m，代表的意义是pat串中最长前缀和后缀相同的长度，lps数组跟txt串没有任何关系，看下面的例子理解一下lps数组的含义：

　　比如lps[4]=2，原因是最大相同的前缀和后缀就是AA。那么如何构造lps数组？这里有点类似动态规划的递推的思路，要有一个变量preLen记录上一次的最大前缀和后缀的长度，现在要求lps[i]，

  1. 如果pat[i] == pat[preLen]，那么自然lps[i] = preLen + 1，同时preLen++
  2. 如果不等，那么更新preLen = lps[preLen - 1]（这里用到这个小技巧，不断利用之前的结果往前推，一旦preLen为0，那么lps[i]只能是0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] lps = new int[m];
// build lps array
int preLen = 0;
int i = 1;
while (i < m) {
  if (pat[preLen] == pat[i]) {
    lps[i] = preLen + 1;
    i++;
    preLen++;
  } else {
    if (preLen == 0) {
      lps[i] = 0;
      i++;
    } else {
      preLen = lps[preLen - 1];
    }
  }
}

　　构造完lps数组之后，开始从txt中寻找子串等于pat，先看一个匹配例子理解一下如何用lps数组：

kmp01.png

kmp02.png

　　贴一下匹配部分代码，里面有注释进行解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int i = 0; // txt字符串的index
int j = 0; // pat字符串的index
while (i < n) {
  if (txt[i] == pat[j]) { // 先判断是否相等，如果相等i和j分别向后移一位
    i++;
    j++;
  }
  if (j == m) { // 匹配到了一个
    System.out.println("Found index :" + (i - j)); 
  } else if (i < n && txt[i] != pat[j]) { // 不想等
    if (j > 0) { //根据lps进行移动，此处是改进暴力匹配
      j = lps[j - 1];
    } else {  // j == 0之间匹配下一个i
      i++;
    }
  }
}

　　算法复杂度 O(n)