#include "stdafx.h"

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>


#
define ALPHABET_LENGTH 256

using namespace std;

bool compareWithRegister(char a, char b) {
  return (a == b);

}

bool compareWithoutRegister(char a, char b) {
  return (tolower(a) == tolower(b));

}

// Префикс-функция
vector < int > prefixFunction(string substr, bool reg) {
  vector < int > d;
  d.reserve(substr.length());
  for (int i = 0; i < substr.length(); i++) {
    d.push_back(0);
  }
  int i = 1;
  int j = 0;
  if (reg) {
    while (i < substr.length()) {
      if (compareWithRegister(substr[i], substr[j])) {
        d[i] = j + 1;
        i++;
        j++;
      } else {
        if (j == 0) {
          d[i] = 0;
          i++;
        } else {
          j = d[j - 1];
        }

      }
    }
  } else {
    while (i < substr.length()) {
      if (compareWithoutRegister(substr[i], substr[j])) {
        d[i] = j + 1;
        i++;
        j++;
      } else {
        if (j == 0) {
          d[i] = 0;
          i++;
        } else {
          j = d[j - 1];
        }

      }
    }
  }

  return d;

}

// Сама функция поиска КМП
void searchKMP(string str, string substr, bool reg) {
  int iterations = 0;
  vector < int > d;
  d.reserve(substr.length());
  d = prefixFunction(substr, reg);
  int k = 0;
  int l = 0;
  if (reg) {
    while ((k != str.length()) && (l != substr.length())) {
      if (compareWithRegister(str[k], substr[l])) {
        k++;
        l++;
        iterations++;
      } else {
        if (l == 0) k++;
        else l = d[l - 1];
        iterations++;
      }
    }

  } else {
    while ((k != str.length()) && (l != substr.length())) {
      if (compareWithoutRegister(str[k], substr[l])) {
        k++;
        l++;
        iterations++;
      } else {
        if (l == 0) k++;
        else l = d[l - 1];
        iterations++;
      }
    }
  }

  if ((k == str.length()) && (l != substr.length())) {
    cout << "Not found with KMP" << endl;
  } else {
    cout << "Found with KMP, index: " << k - l << endl;
  }
  cout << "KMP iterations = " << iterations << endl;

}

// Таблица для БМ-алгоритм
vector < int > bmTable(string substr, bool reg) {

  vector < int > d;
  d.reserve(ALPHABET_LENGTH);
  for (int i = 0; i < ALPHABET_LENGTH; i++)
    d.push_back(-1);

  if (reg)
    for (int i = substr.length() - 1; i > -1; i--)
      d[substr[i]] = i;
  else
    for (int i = substr.length() - 1; i > -1; i--)
      d[tolower(substr[i])] = i;

  return d;
}

void bmSearch(string str, string substr, bool reg) {
  int iterations = 0;
  bool flag = false;
  //Вычислить длину исходной строки
  int n = str.length();

  //Вычислить длину образа
  int m = substr.length();

  //Заполнить таблицу для этого алгоритма
  vector < int > d;
  d.reserve(ALPHABET_LENGTH);
  d = bmTable(substr, reg);

  //Переменная смещения образа по отношению к тексту
  int s = 0;
  if (reg) {
    //Пока s меньше, чем разность длины строки и образа
    while (s <= (n - m)) {
      int j = m - 1;

      //Если образ совпадает со строкой, начиная с конца
      if ((j >= 0) && compareWithRegister(substr[j], str[s + j]))
        while ((j >= 0) && compareWithRegister(substr[j], str[s + j])) {
          j--; //Двигаться от конца образа
          iterations++;
        }
      else {
        iterations++;
      }

      //Если образ полностью совпал со строкой
      if (j < 0) {
        cout << "found " << s << endl;
        flag = true;

        //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
        //таким же символом в образе или на 1, если длины строки не хватает
        if (reg)
          s += ((s + m) < n) ? m - d[str[s + m]] : 1;
        else
          s += ((s + m) < n) ? m - d[tolower(str[s + m])] : 1;
      } else {
        //Сдвинуть образ так, чтобы символ в тексте, не совпавший с символом
        //в образе, совпадал с последним таким же символом в образе или на 1,
        //если совпадающий символ правее текущего символа в образе
        if (reg) {
          if (1 >= (j - d[str[s + j]])) {
            s++;
          } else {
            s += j - d[str[s + j]];
          }

        } else
          s += (1 >= (j - d[tolower(str[s + j])])) ? 1 : (j - d[tolower(str[s + j])]);
      }
    }
  } else {
    while (s <= (n - m)) {
      int j = m - 1;

      //Если образ совпадает со строкой, начиная с конца
      if ((j >= 0) && compareWithRegister(substr[j], str[s + j]))
        while ((j >= 0) && compareWithoutRegister(substr[j], str[s + j])) {
          j--; //Двигаться от конца образа
          iterations++;
        }
      else {
        iterations++;
      }

      //Если образ полностью совпал со строкой
      if (j < 0) {
        cout << "Found with BM, index " << s << endl;
        flag = true;

        //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
        //таким же символом в образе или на 1, если длины строки не хватает
        if (reg)
          s += ((s + m) < n) ? m - d[str[s + m]] : 1;
        else
          s += ((s + m) < n) ? m - d[tolower(str[s + m])] : 1;
      } else {
        //Сдвинуть образ так, чтобы символ в тексте, не совпавший с символом
        //в образе, совпадал с последним таким же символом в образе или на 1,
        //если совпадающий символ правее текущего символа в образе
        if (reg) {
          if (1 >= (j - d[str[s + j]])) {
            s++;
          } else {
            s += j - d[str[s + j]];
          }

        } else
          s += (1 >= (j - d[tolower(str[s + j])])) ? 1 : (j - d[tolower(str[s + j])]);
      }
    }
  }
  // flag нужен, чтобы нот фаунд не выводилось после успешного нахождения
  if ((s > n - m) & !(flag))
    cout << "Not found with BM" << endl;
  cout << "BM iterations = " << iterations << endl;
}

void bruteForceSearch(string str, string substr, bool reg) {
  int iterations = 0;
  bool flag = false;
  int n = str.length();
  int m = substr.length();

  if (reg) {

    //Пройти по строке
    for (int i = 0; i < n - m + 1; i++) {
      //Пройти по образу
      for (int j = 0; j < m; j++) {
        iterations++;
        //Выйти из цикла прохода образа, если найдено несоответствие
        if (!compareWithRegister(str[i + j], substr[j]))
          break;

        //Если образ полностью совпал со строкой, то добавить индекс
        if (j == m - 1) {
          cout << i << endl;
          flag = true;
        }
      }
    }
  } else {
    //Пройти по строке
    for (int i = 0; i < n - m + 1; i++) {
      //Пройти по образу
      for (int j = 0; j < m; j++) {
        iterations++;
        //Выйти из цикла прохода образа, если найдено несоответствие
        if (!compareWithoutRegister(str[i + j], substr[j]))
          break;

        //Если образ полностью совпал со строкой, то добавить индекс
        if (j == m - 1) {
          cout << "Found with BruteForce, index " << i << endl;
          flag = true;
        }
      }
    }
  }
  if (!flag)
    cout << "Not found with BruteForce" << endl;
  cout << "BruteForce iterations = " << iterations << endl;
}

//Объединённый алгоритм поиска Кнута-Морриса-Пратта и Боуера-Мура
void KMPAndBMSearch(string str, string substr, bool reg) {
  int n = str.length();
  int m = substr.length();

  //Заполнить таблицу d
  vector < int > d = prefixFunction(substr, reg);

  //Заполнить таблицу Боуера-Мура
  vector < int > bmT = bmTable(substr, reg);

  //Переменная смещения образа по отношению к тексту
  int s = 0;

  if (reg) {
    //Пока s меньше, чем разность длины строки и образа
    while (s <= (n - m)) {
      int j = m - 1;

      //Пока образ совпадает со строкой, начиная с конца
      while ((j >= 0) && compareWithRegister(substr[j], str[s + j]))
        j--; //Двигаться от конца образа

      //Если образ полностью совпал со строкой
      if (j < 0) {
        cout << "Found, index " << s << endl;

        int k = m;
        while ((k > 0) && !compareWithRegister(substr[k], str[m]))
          k = d[k - 1];

        //Если сдвиг Кнута-Морриса-Пратта больше, чем сдвиг Боуера-Мура
        if (k > (m - bmT[str[s + m]]))
          s += ((s + k) < n) ? k : 1;
        //Иначе
        else
          //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
          //таким же символом в образе
          if (reg)
            s += ((s + m) < n) ? (m - bmT[str[s + m]]) : 1;
          else
            s += ((s + m) < n) ? (m - bmT[tolower(str[s + m])]) : 1;
      }
      //Иначе
      else {
        int i = s + j;
        int k = j;
        while ((k > 0) && !compareWithRegister(substr[k], str[i]))
          k = d[k - 1];

        if (reg) {
          //Если сдвиг Кнута-Морриса-Пратта больше, чем сдвиг Боуера-Мура
          if (k > (j - bmT[str[s + j]]))
            s += ((s + k) < n) ? k : 1;
          //Иначе
          else
            //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
            //таким же символом в образе
            s += ((j - bmT[str[s + j]]) <= 1) ? 1 : (j - bmT[str[s + j]]);
        } else {
          //Если сдвиг Кнута-Морриса-Пратта больше, чем сдвиг Боуера-Мура
          if (k > (j - bmT[tolower(str[s + j])]))
            s += ((s + k) < n) ? k : 1;
          //Иначе
          else
            //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
            //таким же символом в образе
            s += ((j - bmT[tolower(str[s + j])]) <= 1) ? 1 : (j - bmT[tolower(str[s + j])]);
        }
      }
    }
  } else {
    //Пока s меньше, чем разность длины строки и образа
    while (s <= (n - m)) {
      int j = m - 1;

      //Пока образ совпадает со строкой, начиная с конца
      while ((j >= 0) && compareWithoutRegister(substr[j], str[s + j]))
        j--; //Двигаться от конца образа

      //Если образ полностью совпал со строкой
      if (j < 0) {
        cout << "Found, index " << s << endl;

        int k = m;
        while ((k > 0) && !compareWithoutRegister(substr[k], str[m]))
          k = d[k - 1];

        //Если сдвиг Кнута-Морриса-Пратта больше, чем сдвиг Боуера-Мура
        if (k > (m - bmT[str[s + m]]))
          s += ((s + k) < n) ? k : 1;
        //Иначе
        else
          //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
          //таким же символом в образе
          if (reg)
            s += ((s + m) < n) ? (m - bmT[str[s + m]]) : 1;
          else
            s += ((s + m) < n) ? (m - bmT[tolower(str[s + m])]) : 1;
      }
      //Иначе
      else {
        int i = s + j;
        int k = j;
        while ((k > 0) && !compareWithoutRegister(substr[k], str[i]))
          k = d[k - 1];

        if (reg) {
          //Если сдвиг Кнута-Морриса-Пратта больше, чем сдвиг Боуера-Мура
          if (k > (j - bmT[str[s + j]]))
            s += ((s + k) < n) ? k : 1;
          //Иначе
          else
            //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
            //таким же символом в образе
            s += ((j - bmT[str[s + j]]) <= 1) ? 1 : (j - bmT[str[s + j]]);
        } else {
          //Если сдвиг Кнута-Морриса-Пратта больше, чем сдвиг Боуера-Мура
          if (k > (j - bmT[tolower(str[s + j])]))
            s += ((s + k) < n) ? k : 1;
          //Иначе
          else
            //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
            //таким же символом в образе
            s += ((j - bmT[tolower(str[s + j])]) <= 1) ? 1 : (j - bmT[tolower(str[s + j])]);
        }
      }
    }
  }
}

int main() {

  string str = "Hola-Hola girls like Hooligans";
  string substr = "hooligans";

  searchKMP(str, substr, false);
  bmSearch(str, substr, false);
  bruteForceSearch(str, substr, false);
  KMPAndBMSearch(str, substr, false);
  system("PAUSE");
  return 0;
}