#include <iostream>
#include <fstream>
#include <deque>
#include <cmath>

using namespace std;

bool check(string M, deque<char> chars);
void bruteForce(string M, char* filename);
void rabinKarp(string M, char* filename);
void knuthMorrisPratt(string M, char* filename);

int main(int argc, char** argv) {
  bruteForce(argv[1], argv[2]);
  rabinKarp(argv[1], argv[2]);
  knuthMorrisPratt(argv[1], argv[2]);
}

bool check(string M, deque<char> chars) {
  for (int i = 0; i < M.size(); i++)
    if (M[i] != chars[i])
      return false;
  return true;
}

void bruteForce(string M, char* filename) {
  cout << "using brute-force:" << endl;
  ifstream in(filename);
  filebuf* buffer = in.rdbuf();
  deque<char> lastChars;
  unsigned long index = 0;

  for (int i = 0; i < M.size(); i++)
    lastChars.push_back(buffer->sbumpc());
  if (check(M, lastChars))
    cout << "word \"" << M << "\" found in position " << index << endl;
  while (buffer->in_avail() > 0) {
    lastChars.pop_front();
    lastChars.push_back(buffer->sbumpc());
    index++;
    if (check(M, lastChars))
      cout << "word \"" << M << "\" found in position " << index << endl;
  }
  in.close();
  cout << endl;
}

void rabinKarp(string M, char* filename) {
  cout << "using Rabin-Karp:" << endl;
  ifstream in(filename);
  filebuf* buffer = in.rdbuf();
  short q = 131;
  short size = 128;
  short p = 0;
  short t = 0;
  unsigned long index = 0;
  char c;
  deque<char> lastChars;
  long u = (long) pow(size, M.size() - 1) % q;

  for (int i = 0; i < M.size(); i++) {
    p = (size * p + M[i]) % q;
    c = buffer->sbumpc();
    t = (size * t + c) % q;
    lastChars.push_back(c);
  }
  if (p == t && check(M, lastChars))
    cout << "word \"" << M << "\" found in position " << index << endl;

  while (buffer->in_avail() > 0) {
    c = buffer->sbumpc();
    t = ((t - lastChars[0] * u) * size + c) % q;
    if (t < 0)
      t+= q;
    index++;
    lastChars.pop_front();
    lastChars.push_back(c);
    if (p == t && check(M, lastChars))
      cout << "word \"" << M << "\" found in position " << index << endl;
  }
  in.close();
  cout << endl;
}

void knuthMorrisPratt(string M, char* filename) {
  cout << "using Knuth-Morris-Pratt:" << endl;
  ifstream in(filename);
  filebuf* buffer = in.rdbuf();
  unsigned long index = 0;
  char c;
  deque<char> lastChars;
  unsigned short f[M.size() + 1];
  unsigned short j = 0;

  f[0] = 0;
  f[1] = 0;
  cout << "f[1]: " << f[0] << endl;
  for (int i = 2; i <= M.size(); i++) {
    while (j > 0 && M[j] != M[i - 1])
      j = f[j];
    if (M[j] == M[i - 1])
      j++;
    f[i] = j;
    cout << "f[" << i << "]: " << f[i] << endl;
  }

  j = 0;
  while (buffer->in_avail() > 0) {
    c = buffer->sbumpc();
    index++;
    while (j > 0 && M[j] != c)
      j = f[j];
    if (M[j] == c)
      j = j + 1;
    if (j == M.size())
      cout << "word \"" << M << "\" found in position " << (index - M.size()) << endl;
  }
  in.close();
  cout << endl;
}