34

#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;
    int start;
};

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, int start)
{

    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;
    trie[v].start = start;
}

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, int& count)
{

    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);
                count++;
            }

            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, start);
            count++;
        }

        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, int& count, int p_len)
{

    cout << "count = " << count << endl;

    if (count == 0)
    {
        count = t_len-p_len+1;
        cout << count << endl;
        for (int i = 0; i < count; ++i)
        {
            cout << i << " ";
        }
    }

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

        int C[t_len];
        int count_pos = 0;

        for (int i = 0; i < t_len; ++i)
            C[i] = 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;
                        int idx = i - trie[u].depth + 1 - trie[u].start;
                        //cout << C[idx] << endl;
                        if (++C[idx] == count && (p_len+idx-1 < t_len) && idx >= 0)
                        {
                            count_pos++;
                            //cout << "a: " << C[idx] << " " << idx << " " << endl;
                            //cout << idx << endl;
                            //cout << "ПОДЪОДИТ ПОЗ" << idx << endl;
                        }

                    }
                    u = get_suff_link(u, trie);
                    //cout << "Прыгнул в " << u << endl;
                }
            }

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

        cout << endl;
        cout << count_pos << endl;
        for (int i =0; i < t_len; ++i)
            if (C[i] == count && (p_len+i-1 < t_len))
                cout << i << " ";
    }


}

int main()
{

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

    //Если убрать первый ? то ошибка уходит (!)
    //P = "?a";
    //T = "aaa";

    P = "?a";
    T = "aaaa";


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

    int trie_size = 1;
    int max_size = 26 * p_len;
    vertex trie[max_size];
    int count = 0;
    fill_trie(p_len, P, trie, trie_size, count);

    // display(trie,max_size, false);

    search_pattern(t_len, trie, T, count, p_len);






    return 0;
}