KMP算法实现

/*
 * =====================================================================================
 *
 *       Filename:  kmp.cpp
 *
 *    Description:  KMP算法实现 
 *
 *        Version:  1.0
 *        Created:  2009年02月13日 13时19分20秒
 *       Revision:  none *       Compiler:  g++
 *
 *         Author:  Shiquan Ye (mn), [e-mail]
 *        Company:  Wuhan University
 *
 * =====================================================================================
 */
#include <iostream>
#include <string.h>
using namespace std;
int *compute_prefix_function (char *p) {
      int m = strlen(p);
      int k = 0;
      int *x = new int[m];
      x[0] = 0;   
      for (int q = 2; q <= m; q++) {
            while (k > 0 && p[k] != p[q-1])
                  k = x[k-1];
            if (p[k] == p[q-1]) 
                  k++;
            x[q-1] = k;
      }
      return x;
}
void kmp_matcher(char *t, char *p) {
      int n = strlen(t);
      int m = strlen(p);
      int *x = compute_prefix_function(p);
      int q = 0;        /* Number of characters mached */
      
      for (int i = 0; i < n; i++) {         /* Scan the text from left to right */
            while (q > 0 && p[q] != t[i])
                  q = x[q-1];     /* Next character does not match */
            if (p[q] == t[i]) 
                  q++;          /* Next character matches */
            if (q == m) {         /* Is all of p matched */
                  cout<<"Pattern occurs with shift "<<i-m+1<<endl;
                  q = x[q-1];     /* Look for the next match */
            }
      }
}
int main() {
      char *t = "123abcdefg123hijk123";
      char *p = "123";
      kmp_matcher(t, p);
      return 0;
}

运行结果：

Pattern occurs with shift 0
Pattern occurs with shift 10
Pattern occurs with shift 17

 

说明：

算法原理参见算法导论第32章

《算法导论》的字符串第一个位置从1开始，为了不浪费空间，这个程序的字符串的第一个位置从0开始，所以：

Pq表示字符串P[0...q-1]

x[q]表示字符串Pq+1的最长后缀的长度