файл

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


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

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;
        trie[i].depth = 0;
        trie[i].len_end = 0;
        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)
{

    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].end.push_back(end);
    trie[v].len_end++;
}

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)
{

    clean_trie(trie, 26 * p_len);

    int i = 0;
    int start = 0;
    std::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, i - 1);
                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, i);
            count++;
        }
        i++;
    }
}

ofstream out("results.txt");
void search_pattern(int t_len, vertex* trie, std::string T, int& count, int p_len)
{


    if (count == 0)
    {
        count = t_len - p_len + 1;
        out << count << " ";
        for (int i = 0; i < count; ++i)
            out << 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;

            if (trie[v].next[c_idx] == -1)
            {
                while (v > 0 && trie[v].next[c_idx] == -1)
                {
                    v = get_suff_link(v, trie);
                }

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

            else
                v = trie[v].next[c_idx];


            u = v;
            while (u > 0)
            {
                if (trie[u].is_terminal)
                {
                    for (int k = 0; k < trie[u].len_end; ++k)
                    {
                        int idx = i - trie[u].end[k];
                        if (idx >= 0 && idx < t_len && (p_len + idx - 1 < t_len))
                        {
                            C[idx]++;
                            if (C[idx] == count)
                                count_pos++;
                        }
                    }
                }
                u = get_short_link(u, trie);
            }
        }

        out << count_pos << " ";
        for (int i = 0; i < t_len; ++i)
            if (C[i] == count)
                out << i << " ";
    }
}

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;
        //std::cin >> P >> T;
        int p_len = P.length();
        int t_len = T.length();


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

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

        search_pattern(t_len, trie, T, count, p_len);
        out << "\n";
    }
    return 0;
}