#include <iostream>

int main() {
    char text[6][7] = { {'g','g','h','i','a','c','\n'},
                        {'d','g','g','h','i','a','\n'},
                        {'b','c','d','e','f','g','\n'},
                        {'h','i','j','k','a','b','\n'},
                        {'c','d','e','f','g','h','\n'},
                        {'h','i','j','g','h','i','\n'} };
    char pattern[4][4] = { {'g','h','i','\n'},
                          {'d','e','f','\n'},
                          {'j','k','a','\n'},
                          {'\n','\n','\n','\n'} };
    int pattern_length = 3;
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 7; j++)
            std::cout << text[i][j];
    }
    std::cout << '\n';

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            std::cout << pattern[i][j];

    ///hash for pattern
    int hash_pattern_I[3];

    for (int i = 0; i < 3; i++) {
        hash_pattern_I[i] = 26 * 26 * pattern[i][0] + 26 * pattern[i][1] + pattern[i][2];
    }
    for (int i = 0; i < 3; i++)
        std::cout << hash_pattern_I[i] << " ";
    std::cout << '\n';
    std::cout << '\n';

    int hash_pattern_II = (26 * 26 * hash_pattern_I[0] + 26 * hash_pattern_I[1] + hash_pattern_I[2])% 2147483647;
    std::cout << "Hash-ul pattern-ului este: " << hash_pattern_II << '\n';

    int hash_text_I[6][4];
    for (int i = 0; i < 6; i++) {
        hash_text_I[i][0] = 26 * 26 * text[i][0] + 26 * text[i][1] + text[i][2];
    }

    for (int i = 0; i < 6; i++)
        for (int j = 1; j < 4; j++) {
            hash_text_I[i][j] = ((hash_text_I[i][j - 1] - 26 * 26 * text[i][j-1]) * 26 + text[i][j + 2]) % 2147483647;
        }
    std::cout << "Mapa primului hash aplicat pe linii este: " << '\n';
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 4; j++)
            std::cout << hash_text_I[i][j] << " ";
        std::cout << '\n';
    }

    long long hash_text_II[4][4];
    for (int j = 0; j < 4; j++) {
        hash_text_II[0][j] = (26 * 26 * hash_text_I[0][j] + 26 * hash_text_I[1][j] + hash_text_I[2][j]) ;
    }

    int gasit_x;
    int gasit_y;
    for (int j = 0; j < 4; j++)
        for (int i = 1; i < 4; i++)
        {
            hash_text_II[i][j] = ((hash_text_II[i - 1][j] - 26 * 26 * hash_text_I[i - 1][j])*26 + hash_text_I[i + 2][j])% 2147483647;
            if (hash_text_II[i][j] == hash_pattern_II)
            {
                gasit_x = i;
                gasit_y = j;
            }
        }

    std::cout << '\n';
    std::cout << '\n';
    std::cout << "Mapa dupa aplicarea celui de al doilea hash" << '\n';
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            std::cout << hash_text_II[i][j] << " ";
        }
        std::cout << '\n';
    }
        std::cout << '\n';
        std::cout << "Ultima aparitie a pattern-ului in secventa incepe la linia: " << gasit_x << " si coloana: " << gasit_y;
        std::cout << '\n'; std::cout << '\n';
        return 0;
}