file last

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ofstream out("results.txt");

struct vertex
{
    int next[26];
    int go[26];
    int parent;
    char parent_char;
    int link;
    int short_link;
    std::vector<int> end_list;
    bool is_terminal;

};

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].short_link = -1;
        for (int j = 0; j < 26; ++j)
        {
            trie[i].next[j] = -1;
            trie[i].go[j] = -1;
        }
    }
}

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

    int v = 0;
    int c_idx;
    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].short_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].end_list.push_back(end_pos);
}

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];
}

int get_short_link(int v, vertex* trie)
{
    if (trie[v].short_link == -1)
    {
        int u = get_suff_link(v, trie);
        if (trie[u].is_terminal || u == 0)
            trie[v].short_link = u;
        else
            trie[v].short_link = get_short_link(u, trie);
    }

    return trie[v].short_link;
}

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

    clean_trie(trie, 26 * p_len);

    int start = 0;
    std::string mask;
    int len_mask;
    for (int i = 0; i < p_len; ++i)
    {
        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, i - 1);
                count_templates++;
            }

            start = i + 1;
        }
    }

    if (P[p_len - 1] != '?')
    {
        len_mask = p_len - start;
        mask = P.substr(start, len_mask);
        add_string(mask, len_mask, trie, trie_size, p_len - 1);
        count_templates++;
    }
}

void print_answer(int p_len, int t_len, int* C, int count_templates)
{
    int count_pos = 0;
    std::vector<int> ans;
    for (int i = 0; i < t_len; ++i)
    {
        if (C[i] == count_templates && i+p_len <= t_len)
        {
            count_pos++;
            ans.push_back(i);
        }
    }

    out << count_pos << " ";
    for (int i = 0; i < count_pos; ++i)
        out << ans[i] << " ";

}

void search_pattern(int t_len, vertex* trie, std::string T, int& count_templates, int p_len)
{

    int v = 0;
    int u, idx;

    int C[t_len];
    for (int i = 0; i < t_len; ++i)
        C[i] = 0;

    for (int i = 0; i < t_len; ++i)
    {
        v = get_link(v, T[i], trie);

        u = v;
        while (u > 0)
        {
            if (trie[u].is_terminal)
            {
                for (int k = 0; k < trie[u].end_list.size(); ++k)
                {
                    idx = i - trie[u].end_list[k];
                    if (idx >= 0 && idx < t_len)
                        C[idx]++;
                }
            }
            u = get_short_link(u, trie);
        }
    }

    print_answer(p_len, t_len, C, count_templates);

}

void f(std::string P, std::string T)
{
    int p_len = P.length();
    int t_len = T.length();


    int count_templates = 0;
    int trie_size = 1;
    vertex trie[p_len * 26 + 1];

    fill_trie(p_len, P, trie, trie_size, count_templates);

    search_pattern(t_len, trie, T, count_templates, p_len);
}

int main()
{

    int count_tests;
    ifstream ifs("tests.txt");
    ifs >> count_tests;

    for (int i = 0; i < count_tests; ++i)
    {

        std::string P, T;
        ifs >> P >> T;
        f(P, T);

        out << "\n";
    }

    return 0;
}