kmp.cpp

// to compile (using gcc 4.7.2):
// g++ kmp.cpp -std=c++11 -pedantic -o kmp.out
// to run:
// dos2unix <rosalind_kmp.txt | ./kmp.out > kmp.answer

#include <iostream>
#include <vector>
#include <string>

int main()
{    
  std::string p;
  getline(std::cin, p);
  const int m = p.size();
  std::vector<int> b(m+1);

  // Knuth-Morris-Pratt algorithm: Preprocesing
  int i = 0; int j = -1;
  b[i] = j;
  while (i < m) {
    while (j >= 0 && p[i] != p[j]) j = b[j];
    ++i; ++j;
    b[i] = j;
  }
  // `failure array' is now in b[1:m+1)

  for (i=1; i<m; ++i)  std::cout <<b[i] <<' ';
  std::cout <<b[m];
  //std::cout <<std::endl;
  return 0;
}