首页 > 基础算法 > 字符串处理 > 常用算法-KMP算法[含代码]
2014
02-19

常用算法-KMP算法[含代码]

KMP算法的基础部分不再多说,详细大家都Google过了。这里做一些总结。

对于KMP算法来说,重点就是 next数组 (也有叫覆盖函数,部分匹配表,lps数组等)。

总之就是 对模式串做预处理,而且该预处理只和 模式串(pattern)本身有关!

假设有模式串 pattern = “abababca”;  则有匹配表:

char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

 

下面介绍《部分匹配表》是如何产生的。

首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

字符串:   "bread"

前缀: b , br, bre, brea

后缀:  read, ead, ad ,  d

 

关于 next数组 (也有叫覆盖函数,部分匹配表,lps数组) 的

通俗解释:”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

   - "A"的前缀和后缀都为空集,共有元素的长度为0;
  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

20295924K-0

pattern “AABAACAABAA”, next[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
pattern “ABCDE”, next[] is [0, 0, 0, 0, 0]
pattern “AAAAA”, next[] is [0, 1, 2, 3, 4]
pattern “AAABAAA”, next[] is [0, 1, 2, 0, 1, 2, 3]
pattern “AAACAAAAAC”, next[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

下面的代码实现中,lps(longest prefix suffix )数组就是我们说的next数组。这个是最原创的实现,和网上很多优化的next数组的算法不同,但是基本原理是一样的:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void computeLPSArray(char *pat, int M, int *lps);

void KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    // 预处理pattern,计算出 lps[]数组记录前缀和后缀的最长匹配
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    while(i < N)
    {
      if(pat[j] == txt[i])
      {
        j++;
        i++;
      }

      if (j == M)
      {
        printf("Found pattern at index %d \n", i-j);
        j = lps[j-1];
      }

      // mismatch after j matches
      else if(pat[j] != txt[i])
      {
        // Do not match lps[0..lps[j-1]] characters,
        // they will match anyway
        if(j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
    free(lps); // to avoid memory leak
}

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // 记录前一个[最长匹配的前缀和后缀]的长度
    int i;

    lps[0] = 0; // lps[0] 必须是 0
    i = 1;

    // the loop calculates lps[i] for i = 1 to M-1
    while(i < M)
    {
       if(pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if( len != 0 )
         {
           // 这个地方有陷阱. 考虑这个例子 AAACAAAA ,i = 7.
           len = lps[len-1];

           // 另外, 注意 i 在这个地方并没有增加
         }
         else // 如果 (len == 0)
         {
           lps[i] = 0; //没有一个匹配的
           i++;
         }
       }
    }
}

// 测试
int main()
{
   char *txt = "ABABDABACDABABCABAB";
   char *pat = "ABABCABAB";
   KMPSearch(pat, txt);
   return 0;
}

测试数据如下:

1) Input:

txt[] =  "THIS IS A TEST TEXT"
pat[] = "TEST"

Output:

Pattern found at index 10

2) Input:

txt[] =  "AABAACAADAABAAABAA"
pat[] = "AABA"

Output:

Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。