2

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct vertex
{
    bool is_terminal;
    int next[26];
    int go[26];
    int parent;
    char parent_char;
    int link;
    int depth;
};

void clean_trie(vertex* trie, int size)
{
    for (int i = 0; i < size; ++i)
    {
        trie[i].is_terminal = false;
        trie[i].parent = -1;
        trie[i].link = -1;
        trie[i].depth = 0;
        for (int j = 0; j < 26; ++j)
        {
            trie[i].next[j] = -1;
            trie[i].go[j] = -1;
        }
    }
}

void add_string(string s, int s_len, vertex* trie, int& size)
{

    // cout << "add: " << s << endl;
    int v = 0;
    int c_idx;
    vertex buff;
    char c;

    for (int i = 0; i < s_len; ++i)
    {
        c = s[i];
        c_idx = static_cast<int>(c) - 97;

        if (trie[v].next[c_idx] == -1)
        {
            trie[size].link = -1;
            trie[size].parent = v;
            trie[size].parent_char = c;
            trie[v].next[c_idx] = size++;
        }

        v = trie[v].next[c_idx];
    }
    trie[v].is_terminal = true;
    trie[v].depth = s_len;
}

int get_link(int v, char c, vertex* trie);

int get_suff_link(int v, vertex* trie)
{
    if (trie[v].link == -1)
    {
        if (v == 0 || trie[v].parent == 0)
            trie[v].link = 0;
        else
            trie[v].link = get_link(get_suff_link(trie[v].parent, trie), trie[v].parent_char, trie);
    }
    return trie[v].link;
}

int get_link(int v, char c, vertex* trie)
{

    int c_idx = static_cast<int>(c) - 97;

    if (trie[v].go[c_idx] == -1)
    {
        if (trie[v].next[c_idx] != -1)
            trie[v].go[c_idx] = trie[v].next[c_idx];

        else if (v == 0)
            trie[v].go[c_idx] = 0;

        else
            trie[v].go[c_idx] = get_link(get_suff_link(v, trie), c, trie);
    }

    return trie[v].go[c_idx];
}

void fill_trie(int p_len, string P, vertex* trie, int& trie_size)
{

    clean_trie(trie, 26 * p_len);

    int i = 0;
    int start = 0;
    string mask;
    int len_mask;
    while (i < p_len)
    {
        if (P[i] == '?')
        {
            if (i - start > 0)
            {
                len_mask = i - start;
                mask = P.substr(start, len_mask);
                add_string(mask, len_mask, trie, trie_size);
            }

            start = i + 1;
        }

        else if (i == p_len - 1)
        {
            len_mask = i - start + 1;
            mask = P.substr(start, len_mask);
            add_string(mask, len_mask, trie, trie_size);
        }

        i++;
    }
}

void display(vertex* trie, int size, bool display_links)
{
    for (int i = 0; i < size; ++i)
    {
        bool flag = true;
        for (int j = 0; j < 26; ++j)
        {
            if (trie[i].next[j] >= 0)
            {
                if (flag)
                {
                    if (trie[i].is_terminal)
                        cout << "vertex " << i << ": (is_terminal) ";
                    else
                        cout << "vertex " << i << ": ";
                    flag = false;
                }
                cout << char(j + 97) << "->" << trie[i].next[j] << " ";
            }
        }
        if (not flag)
            cout << endl;
        if (flag && trie[i].is_terminal)
            cout << "vertex " << i << ": (is_terminal);" << endl;
    }

    if (display_links)
    {
        cout << "\n Ссылки:" << endl;
        for (int v = 0; v < size; ++v)
        {
            cout << "vertex: " << v << "  ";
            cout << "suff: " << get_suff_link(v, trie) << ";  ";
            cout << "get_link: ";
            for (int j = 0; j < 26; ++j)
            {
                int z = get_link(v, char(j + 97), trie);
                if (z > 0)
                    cout << "(" << char(j + 97) << "," << z << ") ";
            }
            cout << endl;
        }
    }
}

void search_pattern(int t_len, vertex* trie, string T)
{

    char c;
    int v = 0;
    int u;
    int c_idx;
    int start = 0;

    for (int i = 0; i < t_len; ++i)
    {
        c = T[i];
        c_idx = static_cast<int>(c) - 97;

        cout << "\n Текущий символ: " << c << ", текущая вершина: " << v << endl;

        //Если нет пути
        if (trie[v].next[c_idx] == -1)
        {
            cout << "Нет пути - прыгаем по суфф ссылкам из вершины " << v << endl;
            //то прыгаем по суфф сылкам назад пока не найдем путь
            while (v > 0 && trie[v].next[c_idx] == -1)
            {
                v = get_suff_link(v, trie);
                cout << "прыгнул в " << v << "; ";
            }
            cout << endl;

            if (trie[v].next[c_idx] != -1)
            {
                cout << "Нашли путь, переходим в вершину " << trie[v].next[c_idx] << endl;
                v = trie[v].next[c_idx];
            }
            else
            {
                cout << "Путь не найден, сидим в корне, vertex: " << v << endl;
            }
        }
        else
        {
            cout << "Путь есть, переходим по ребру в вершину " << trie[v].next[c_idx] << endl;
            v = trie[v].next[c_idx];
        }

        //если терминальная принтим и потом бежим по суфф ссылкам до корня в поисках других
        //терминальных
        if (trie[v].is_terminal)
        {
            cout << "Вершина " << v << " оказалась терминальной " << endl;
            u = v;
            cout << "Начинаю прыгать по суфф ссылкам: " << endl;
            while (u > 0)
            {
                if (trie[u].is_terminal)
                {
                    cout << u << "- терминальная -  принтим: ";
                    cout << "(" << i - trie[u].depth + 1 << "," << i << ")" << endl;
                }
                u = get_suff_link(u, trie);
                cout << "Прыгнул в " << u << endl;
            }
        }

        else
            cout << "Не терминальная, ждём некст символ " << endl;
        //если нет то просто ожидаем некст символ
    }
}


int main()
{

    string P, T;
    // cin >> P >> T;
    // P = "he?she?his?hers";
    P = "";
    // P = "abcd";
    T = "sheyuihe";

    int p_len = P.length();
    int t_len = T.length();

    int trie_size = 1;
    int max_size = 26 * p_len;
    vertex trie[max_size];

    fill_trie(p_len, P, trie, trie_size);

    // display(trie,max_size, false);

    search_pattern(t_len, trie, T);


    return 0;
}