#include<iostream>
#include<stdio.h>
#include<vector>
#include<sstream>
#include<map>
#include<fstream>
#include<omp.h>


using namespace std;

 // Хэш-функция, переводит строку в хэш
long long HashFun(string s) {
    const int k = 31, mod = 1e9 + 7;

    long long h = 0, m = 1;
    for (char c : s) {
        int x = (int)(c - 'a' + 1);
        h = (h + m * x) % mod;
        m = (m * k) % mod;
    }
    return h;
}

// Алгоритм Рабина-карпа для поиска подстроки в строке с помощью хэшей этих строк
bool RabinKarp(string in_string, string tofind_string)
{
    long long in_hash = HashFun(in_string);
    long long to_find_hash = HashFun(tofind_string);
    // Сравнивание хэшей строк
    if (in_hash == to_find_hash)
    {
        // посимвольное сравнивание 2 строк
        for (int i = 0; i < in_string.length(); i++)
        {
            if (in_string[i] != tofind_string[i])
            {
                return false;
            }
        }
        return true;
    }
    return false;
}

int main()
{
    setlocale(LC_ALL, "Rus");
    string to_find_string;
    ifstream initial_string(".\\initial_string.txt"); // Открываем стрим для считывания текстового файла с исходной строкой
    cout << "Введите искомую строку:" << endl;
    getline(cin, to_find_string); // Читаем подстроку, которую надо найти в исходной с консоли
    bool flag = false;
    initial_string.seekg(0, ios_base::end); // Перемещаем указатель ввода на последнюю позицию
    long long string_len = initial_string.tellg(); // Смотрим позицию курсора(конец файла на данный момент)
    int to_find_len = to_find_string.length(); // Длина введенной подстроки
    int thread_count = 2;
    //длина строки без последней части чтобы не выходить за пределы
    int length_read = string_len - to_find_len + 1; // Длина исходной строки без длины подстроки
    omp_set_num_threads(thread_count); // Ставим кол-во потоков по умолчанию на 2
    double start_time;
    double end_time;
    start_time = omp_get_wtime();
    int i;
#pragma omp parallel shared(flag) private(i) // Для каждого потока своя i, но общий flag
    {
#pragma omp for
        for (i = 0; i <= length_read; i++)
        {
            int word_start = i * to_find_len;
            int word_finish = (i + 1) * to_find_len;

            char* current_word = new char[to_find_len]; // Объявляем динамический симсвольный массив на размер текущего слова

            initial_string.seekg(i, ios_base::beg); // Ставим на текущую позицию индексатора цикла
            initial_string.get(current_word, to_find_len + 1); // Вырезаем текущее слово из строки и перемещаем в динам массив

            if (RabinKarp(current_word, to_find_string)) // Используем алгоритм робина-карпа, чтобы сравнить строки
                flag = true;
        }
    }
    end_time = omp_get_wtime();
    printf("Параллельный %f сек\n", end_time - start_time);
    if (flag == false)
    {
        cout << "Нет совпадения" << endl;
    }
    else
    {
        cout << "есть совпадения" << endl;
    }
}