前言

    本节介绍Knuth-Morris-Pratt字符串匹配算法(简称KMP算法)。该算法最主要是构造出模式串pat的前缀和后缀的最大相同字符串长度数组next，和前面介绍的《朴素字符串匹配算法》不同，朴素算法是当遇到不匹配字符时，向后移动一位继续匹配，而KMP算法是当遇到不匹配字符时，不是简单的向后移一位字符，而是根据前面已匹配的字符数和模式串前缀和后缀的最大相同字符串长度数组next的元素来确定向后移动的位数，所以KMP算法的时间复杂度比朴素算法的要少，并且是线性时间复杂度，即预处理时间复杂度是O(m)，匹配时间复杂度是O(n)。

KMP字符串匹配算法实现

    首先介绍下前缀和后缀的基本概念：

    前缀：字符串中除了最后一个字符，前面剩余的其他字符连续构成的字符或字符子串称为该字符串的前缀；

    后缀：字符串中除了首个字符，后面剩余的其他字符连续构成的字符或字符子串称为该字符串的后缀；

    注意：空字符是任何字符串的前缀，同时也是后缀；

    例如：字符串“Pattern”的前缀是：“P”“Pa”“Pat”“Patt”“Patte”“Patter”；

          后缀是：“attern”“ttern”“tern”“ern”“rn”“n”；

    在进行KMP字符串匹配时，首先要求出模式串的前缀和后缀的最大相同字符串长度数组next；下面先看下例子模式串pat=abababca的数组next：其中value值即为next数组内的元素值，index是数组下标标号；

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 |

－"abababca"的前缀为[a, ab, aba, abab, ababa，ababab，abababc]，后缀为[bababca, ababca, babca, abca, bca, ca,a]，最大相同字符子串[a]的长度为1。

模式串的前缀和后缀的最大相同字符串长度数组next的递推求解步骤：

1. 若P[i]=P[len]，则next[i]=++len；i++继续查找下一个字符的next元素值；
2. 若P[i]！=P[len]，则分为两步：

• 若len！=0，递归查找，即比较next前一个元素值所在位置的字符P[next[len-1]]与P[i]，因此i不变，而len=len-1；
• 若len=0，则当前字符的next元素值为0，即next[i]=0；此时len不变，i++查找下一个位置字符的next元素值；

void computeNextArray(const string &pat, int M, int *next)
{
    int len = 0;  // lenght of the previous longest prefix suffix
	int i = 1;
    next[0] = 0; // next[0] is always 0    
 
    // the loop calculates next[i] for i = 1 to M-1
    while(i < M)
    {
		   if(pat[i] == pat[len])
		   {
			 len++;
			 next[i] = len;
			 i++;
		   }
		   else // (pat[i] != pat[len])
		   {
				 if( len != 0 )
				 {// This is tricky. Consider the example AAACAAAA and i = 7.
				   len = next[len-1]; 
				   // Also, note that we do not increment i here
				 }
				 else // if (len == 0)
				 {
				   next[i] = 0;
				   i++;
				 }
		   }
    }
}

1. 若当前对应字符匹配成功即pat[j] = txt[i]，则i++，j++，继续匹配下一个字符；
2. 若当前对应字符匹配失败即pat[j] ！= txt[i]，则分为两步：

• 若模式串当前字符的位置j！=0时，文本字符串当前位置i不变，更新模式串当前字符的位置j = next[j-1]；此时，模式串相对于文本字符串向后移动j - next[j-1]位，继续匹配字符；
• 若模式串当前字符的位置j=0时，此时只需更新文本字符串的当前位置i++，其他不变，继续匹配下一个字符；

    源码实现如下：

void KMPSearch(const string &pat, const string &txt)
{
    int M = pat.length();
    int N = txt.length();
 
    // create next[] that will hold the longest prefix suffix values for pattern
    int *next = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]
 
    // Preprocess the pattern (calculate next[] array)
    computeNextArray(pat, M, next);
 
    int i = 0;  // index for txt[]
    while(i < N)
    {
      if(pat[j] == txt[i])
      {
        j++;
        i++;
      }
 
      if (j == M)
      {
        cout<<"Found pattern at index:"<< i-j<<endl;
        j = next[j-1];
      }
 
      // mismatch after j matches
      else if(pat[j] != txt[i])
      {
        // Do not match next[0..next[j-1]] characters,
        // they will match anyway
        if(j != 0)
         j = next[j-1];
        else
         i = i+1;
      }
    }
    free(next); // to avoid memory leak
}

    由上面可知next表元素值如下

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 |

    第一次匹配成功的字符为相对应字符a，由于模式串下一个字符b与文本字符c不匹配，且j=0、已匹配字符数为len=1，next[len-1]=0；所以模式串与下一个文本字符串字符匹配，直到匹配成功；

bacbababaabcbab
 |
 abababca

bacbababaabcbab
    |||||
    abababca

// x denotes a skip

bacbababaabcbab
    xx|||
      abababca

// x denotes a skip

bacbababaabcbab
      xx|
        abababca

完整程序：

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

using namespace std;
 
void computeNextArray(const string &pat, int M, int *next);
 
void KMPSearch(const string &pat, const string &txt)
{
    int M = pat.length();
    int N = txt.length();
 
    // create next[] that will hold the longest prefix suffix values for pattern
    int *next = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]
 
    // Preprocess the pattern (calculate next[] array)
    computeNextArray(pat, M, next);
 
    int i = 0;  // index for txt[]
    while(i < N)
    {
      if(pat[j] == txt[i])
      {
        j++;
        i++;
      }
 
      if (j == M)
      {
        cout<<"Found pattern at index:"<< i-j<<endl;
        j = next[j-1];
      }
 
      // mismatch after j matches
      else if(pat[j] != txt[i])
      {
        // Do not match next[0..next[j-1]] characters,
        // they will match anyway
        if(j != 0)
         j = next[j-1];
        else
         i = i+1;
      }
    }
    free(next); // to avoid memory leak
}
 
void computeNextArray(const string &pat, int M, int *next)
{
    int len = 0;  // lenght of the previous longest prefix suffix
	int i = 1;
    next[0] = 0; // next[0] is always 0    
 
    // the loop calculates next[i] for i = 1 to M-1
    while(i < M)
    {
		   if(pat[i] == pat[len])
		   {
			 len++;
			 next[i] = len;
			 i++;
		   }
		   else // (pat[i] != pat[len])
		   {
				 if( len != 0 )
				 {// This is tricky. Consider the example AAACAAAA and i = 7.
				   len = next[len-1]; 
				   // Also, note that we do not increment i here
				 }
				 else // if (len == 0)
				 {
				   next[i] = 0;
				   i++;
				 }
		   }
    }
}
 
int main()
{
   string txt = "ABABDABACDABABCABAB";
   string pat = "ABABCABAB";
   KMPSearch(pat, txt);
   system("pause");
   return 0;
}

《算法导论》

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

http://blog.csdn.net/v_july_v/article/details/7041827

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm

http://www.cnblogs.com/gaochundong/p/string_matching.html

http://dsqiu.iteye.com/blog/1700312

算法——字符串匹配之KMP算法