Knuth-Morris-Pratt Algorithm

kmp.cpp

/*
 * =====================================================================================
 *
 *       Filename:  kmp.cpp
 *
 *    Description:  Knuth-Morris-Pratt Algorithm
 *
 *        Version:  1.0
 *        Created:  10/04/2013 06:15:30 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ji.Zhilong (), zhilongji@gmial.com
 *   Organization:  SJTU
 *
 * =====================================================================================
 */
#include <vector>
#include <string>
#include <iostream>

using namespace std;

vector<int> kmp(const string &pat, const string &txt)
{
  vector<int> skiptable(pat.size(), 0);

  for (int i = 1; i < pat.size(); i++)
  {
  int p = skiptable[i - 1];
	while (p != 0 && pat[p] != pat[i])
	  p = skiptable[p];
	if (pat[p] == pat[i])
	  skiptable[i] = p + 1;
  }

  vector<int> result;
  int p = 0;

  for (int i = 0; i < txt.size(); i++)
  {
	if (txt[i] == pat[p]) {
	  p += 1;
	  if (p == pat.size()) {
		result.push_back(i - p + 1);
		p = skiptable.back();
	  }} 
	else {
	  p = skiptable[p];
	}
  }

  return result;
}


int
main()
{
  string pat = "abab";
  string txt = "defabababedabab";
  vector<int> result = kmp(pat, txt);

  for (vector<int>::iterator it=result.begin(); it != result.end(); it++)
	cout << *it << endl;
}