---

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

// Размер хеш-таблицы.
// Лучше брать простое число, чтобы было меньше коллизий.
const int SIZE = 31;

// Максимальное количество позиций одного слова в тексте.
const int MAX_POS = 1000;

// Один элемент хеш-таблицы.
// Он хранит слово, позиции этого слова и ссылку на следующий элемент.
struct Node {
    string word;             // слово
    int positions[MAX_POS];  // массив позиций слова в тексте
    int count;               // сколько раз слово найдено
    Node* next;              // следующий элемент в цепочке
};

// Хеш-таблица.
// Это массив указателей на элементы Node.
Node* table[SIZE];

// Перевод английских заглавных букв в маленькие.
string toLower(string s) {
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] = s[i] + 32;
        }
    }

    return s;
}

// Хеш-функция.
// Считает сумму кодов символов слова
// и берёт остаток от деления на размер таблицы.
int hashFunc(string word) {
    int sum = 0;

    for (int i = 0; i < word.length(); i++) {
        sum += word[i];
    }

    return sum % SIZE;
}

// Алгоритм Бойера-Мура.
// Ищет все позиции слова word в тексте text.
// Позиции записываются в массив positions.
// Количество найденных позиций записывается в count.
void boyerMoore(string text, string word, int positions[], int& count) {
    count = 0;

    int n = text.length(); // длина текста
    int m = word.length(); // длина слова

    // Если слово пустое или длиннее текста, искать нечего.
    if (m == 0 || m > n) {
        return;
    }

    // Таблица смещений.
    int shiftTable[256];

    // Сначала для всех символов сдвиг равен длине слова.
    for (int i = 0; i < 256; i++) {
        shiftTable[i] = m;
    }

    // Для символов, которые есть в слове,
    // задаём свои смещения.
    for (int i = 0; i < m - 1; i++) {
        shiftTable[(unsigned char)word[i]] = m - 1 - i;
    }

    // pos — позиция в тексте, с которой прикладываем слово.
    int pos = 0;

    while (pos <= n - m) {
        // Сравнение начинаем с последнего символа слова.
        int j = m - 1;

        // Сравниваем справа налево.
        while (j >= 0 && word[j] == text[pos + j]) {
            j--;
        }

        // Если j < 0, значит все символы совпали.
        if (j < 0) {
            if (count < MAX_POS) {
                positions[count] = pos;
                count++;
            }

            // Сдвигаемся на 1, чтобы найти следующие вхождения.
            pos++;
        } else {
            // Если символы не совпали, делаем сдвиг по таблице.
            pos += shiftTable[(unsigned char)text[pos + m - 1]];
        }
    }
}

// Добавление слова в хеш-таблицу.
void addWord(string word, int positions[], int count) {
    int index = hashFunc(word);

    // Если такое слово уже есть, просто обновляем его позиции.
    Node* current = table[index];

    while (current != NULL) {
        if (current->word == word) {
            current->count = count;

            for (int i = 0; i < count; i++) {
                current->positions[i] = positions[i];
            }

            return;
        }

        current = current->next;
    }

    // Если слова ещё нет, создаём новый элемент.
    Node* newNode = new Node;

    newNode->word = word;
    newNode->count = count;

    // Копируем позиции в новый элемент.
    for (int i = 0; i < count; i++) {
        newNode->positions[i] = positions[i];
    }

    // Добавляем элемент в начало цепочки.
    newNode->next = table[index];
    table[index] = newNode;
}

// Поиск слова в хеш-таблице.
Node* searchWord(string word) {
    int index = hashFunc(word);

    Node* current = table[index];

    // Проходим по цепочке в нужной ячейке.
    while (current != NULL) {
        if (current->word == word) {
            return current;
        }

        current = current->next;
    }

    return NULL;
}

// Удаление слова из хеш-таблицы.
void deleteWord(string word) {
    int index = hashFunc(word);

    Node* current = table[index];
    Node* previous = NULL;

    while (current != NULL) {
        if (current->word == word) {
            // Если удаляем первый элемент цепочки.
            if (previous == NULL) {
                table[index] = current->next;
            }
            // Если удаляем элемент из середины или конца.
            else {
                previous->next = current->next;
            }

            delete current;

            cout << "Слово удалено" << endl;
            return;
        }

        previous = current;
        current = current->next;
    }

    // Если слова нет в хеш-таблице.
    cout << "-1" << endl;
}

// Вывод позиций найденного слова.
void printPositions(Node* node) {
    // Если слова нет в таблице или оно не найдено в тексте.
    if (node == NULL || node->count == 0) {
        cout << "-1" << endl;
        return;
    }

    cout << "Позиции слова в тексте: ";

    for (int i = 0; i < node->count; i++) {
        cout << node->positions[i] << " ";
    }

    cout << endl;
}

// Вывод всей хеш-таблицы на экран.
void printHashTable() {
    cout << "\nХеш-таблица:" << endl;

    for (int i = 0; i < SIZE; i++) {
        cout << i << ": ";

        Node* current = table[i];

        // Если ячейка пустая.
        if (current == NULL) {
            cout << "пусто";
        }

        // Если в ячейке есть элементы, выводим цепочку.
        while (current != NULL) {
            cout << current->word << " [";

            if (current->count == 0) {
                cout << "-1";
            } else {
                for (int j = 0; j < current->count; j++) {
                    cout << current->positions[j];

                    if (j < current->count - 1) {
                        cout << ", ";
                    }
                }
            }

            cout << "]";

            // Если есть следующий элемент, показываем цепочку.
            if (current->next != NULL) {
                cout << " -> ";
            }

            current = current->next;
        }

        cout << endl;
    }
}

int main() {
    setlocale(LC_ALL, "Russian");

    // Изначально все ячейки хеш-таблицы пустые.
    for (int i = 0; i < SIZE; i++) {
        table[i] = NULL;
    }

    // Открываем входные файлы.
    ifstream textFile("text.txt");
    ifstream wordsFile("words.txt");

    if (!textFile.is_open()) {
        cout << "Не удалось открыть файл text.txt" << endl;
        return 0;
    }

    if (!wordsFile.is_open()) {
        cout << "Не удалось открыть файл words.txt" << endl;
        return 0;
    }

    string text = "";
    string line;

    // Считываем весь текст из text.txt в одну строку.
    while (getline(textFile, line)) {
        text += line + " ";
    }

    textFile.close();

    // Переводим текст в нижний регистр.
    text = toLower(text);

    string word;
    int positions[MAX_POS];
    int count;

    // Считываем слова из words.txt.
    // Для каждого слова ищем позиции и добавляем его в хеш-таблицу.
    while (wordsFile >> word) {
        word = toLower(word);

        boyerMoore(text, word, positions, count);

        addWord(word, positions, count);
    }

    wordsFile.close();

    cout << "Хеш-таблица создана." << endl;

    int choice;

    do {
        cout << "\nМеню:" << endl;
        cout << "1 - найти слово" << endl;
        cout << "2 - добавить слово" << endl;
        cout << "3 - удалить слово" << endl;
        cout << "4 - вывести хеш-таблицу" << endl;
        cout << "0 - выход" << endl;
        cout << "Выбор: ";
        cin >> choice;

        if (choice == 1) {
            cout << "Введите слово для поиска: ";
            cin >> word;

            word = toLower(word);

            Node* found = searchWord(word);

            printPositions(found);
        }

        else if (choice == 2) {
            cout << "Введите слово для добавления: ";
            cin >> word;

            word = toLower(word);

            // Ищем позиции нового слова в тексте.
            boyerMoore(text, word, positions, count);

            // Добавляем слово в хеш-таблицу.
            addWord(word, positions, count);

            cout << "Слово добавлено." << endl;

            // Если слово в тексте не найдено, по заданию выводим -1.
            if (count == 0) {
                cout << "-1" << endl;
            } else {
                cout << "Позиции слова в тексте: ";

                for (int i = 0; i < count; i++) {
                    cout << positions[i] << " ";
                }

                cout << endl;
            }
        }

        else if (choice == 3) {
            cout << "Введите слово для удаления: ";
            cin >> word;

            word = toLower(word);

            deleteWord(word);
        }

        else if (choice == 4) {
            printHashTable();
        }

        else if (choice == 0) {
            cout << "Выход из программы." << endl;
        }

        else {
            cout << "Ошибка: неверная команда" << endl;
        }

    } while (choice != 0);

    return 0;
}