KMP

kmp.cpp

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

using namespace std;

// This one uses a slightly different table
// It's probably easier to remember.
// The table LPS contains at LPS[i] the size of the Longest Proper Prefix of p[0..i] that is also a Suffix of p[0..i]. 
vector<int> computeLPS(string& p)
{
  vector<int> result(p.size(), 0);

  int longest_proper_prefix_end = 0;

  result[0] = 0;
  for (int i = 1; i < p.size(); i++)
  {
      if (p[i] == p[longest_proper_prefix_end])
      {
          longest_proper_prefix_end++;
          result[i] = longest_proper_prefix_end;
      }
      else
      {
          longest_proper_prefix_end = 0;
          result[i] = 0;
      }
  }

  return result;
}

int main()
{
  string s;
  string p;
  cin >> s >> p;

  auto lps = computeLPS(p);
  
  int i = 0;
  int j = 0;
  while (i <= s.size())
  {
      if (p[j] == s[i])
      {
          j++;
          i++;
      }

      if (j == p.size())
      {
          cerr << "found at index " << i-j << endl;
          j = lps[j - 1];
          goto found;
      }
      else if (p[j] != s[i])
      {
          cerr << "mismatch at index " << i-j << " with pattern index " << j << endl;
          if (j == 0)
          {
              i++;
          }
          else
          {
              j = lps[j - 1];
          }
      }
  }

not_found:
  cout << "not found" << endl;
  return 0;

found:
  cout << "found" << endl;
  return 0;
}

kmp_count.cpp

#include <string>
#include <vector>

using namespace std;

vector<int> createTable(string const & W) {
  vector<int> result(W.size() + 1, 0);
  result[0] = -1;
  int x = 0;
  for (int i {1}; i < W.size(); i++) {
      if (W[i] == W[x]) {
          result[i] = result[x];
          x++;
      } else {
          result[i] = x;
          x = 0;
      }
  }
  result[W.size()] = x;
  return result;
}

// Uses the KMP algorithm to count the number of occurences of W in S.
// T is a table that can be computed with createTable.
int kmpCount(string const & W, string const & S, vector<int> const & T) {
  int count = 0;
  int m = 0;
  int i = 0;
  while (m < S.size()) {
      if (W[i] == S[m + i]) {
          i = i + 1;
          if (i == W.size()) {
              count += 1;
              m = m + i - T[W.size()];
              i = T[W.size()];
          }
      } else {
          m = m + i - T[i];
          i = T[i] == -1 ? 0 : T[i];
      }
  }
  return count;
}