Aho-Korasik_2

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <array>
#include <utility>
#include <algorithm>

const int N = 5;
const char WILDCARD = '?';

std::vector<std::string> patterns;
std::array<char, N> alphabet = { 'A', 'C', 'T', 'G', 'N' };

struct Node {
    std::map<char, Node*> son;
    std::map<char, Node*> go;
    Node* parent;
    Node* suffLink;
    Node* up;
    char charToParent;
    bool isTerminal;
    std::vector<int> leafPatternNumber;

    Node() {
        son = { {alphabet[0], NULL}, {alphabet[1], NULL}, {alphabet[2], NULL}, {alphabet[3], NULL}, {alphabet[4], NULL}, };
        go = { {alphabet[0], NULL}, {alphabet[1], NULL}, {alphabet[2], NULL}, {alphabet[3], NULL}, {alphabet[4], NULL}, };
        parent = nullptr;
        suffLink = nullptr;
        up = nullptr;
        charToParent = ' ';
        isTerminal = false;
    }
};

struct Trie {
    Node* root;

    Trie() {
        root = new Node();
    }

    Node* getSuffLink(Node* v) {
        if (v->suffLink == nullptr) {
            if (v == root || v->parent == root) {
                v->suffLink = root;
            }
            else {
                v->suffLink = getLink(getSuffLink(v->parent), v->charToParent);
            }
        }
        return v->suffLink;
    }

    Node* getLink(Node* v, char c) {
        if (v->go[c] == nullptr) {
            if (v->son[c]) {
                v->go[c] = v->son[c];
            }
            else if (v == root) {
                v->go[c] = root;
            }
            else {
                v->go[c] = getLink(getSuffLink(v), c);
            }
        }
        return v->go[c];
    }

    Node* getUp(Node* v) {
        if (v->up == nullptr) {
            if (getSuffLink(v)->isTerminal) {
                v->up = getSuffLink(v);
            }
            else if (getSuffLink(v) == root) {
                v->up = root;
            }
            else {
                v->up = getUp(getSuffLink(v));
            }
        }
        return v->up;
    }

    void addString(const std::string& s, int patternNumber) {
        Node* curr = root;
        for (char c : s) {
            if (curr->son[c] == nullptr) {
                curr->son[c] = new Node();
                curr->son[c]->parent = curr;
                curr->son[c]->charToParent = c;
            }
            curr = curr->son[c];
        }
        curr->isTerminal = true;
        curr->leafPatternNumber.push_back(patternNumber);
    }

    void processText(const std::string& text, std::vector<std::pair<int, int>>& results) {
        Node* curr = root;
        for (size_t i = 0; i < text.length(); ++i) {
            char c = text[i];
            curr = getLink(curr, c);
            Node* checkNode = curr;
            while (checkNode != root) {
                if (checkNode->isTerminal) {
                    for (int patNum : checkNode->leafPatternNumber) {
                        results.push_back({ i + 2 - patterns[patNum].length(), patNum + 1 });
                    }
                }
                checkNode = getUp(checkNode);
            }
        }
    }
};

std::vector<int> findPatternWithWildcards(const std::string& text, const std::string& pattern, char wildcard) {
    std::vector<std::string> subPatterns;
    std::vector<int> startPositions;
    std::string currentSubPattern;
    for (size_t i = 0; i < pattern.length(); ++i) {
        if (pattern[i] == wildcard) {
            if (!currentSubPattern.empty()) {
                subPatterns.push_back(currentSubPattern);
                startPositions.push_back(i - currentSubPattern.length() + 1);
                currentSubPattern.clear();
            }
        }
        else {
            currentSubPattern += pattern[i];
        }
    }
    if (!currentSubPattern.empty()) {
        subPatterns.push_back(currentSubPattern);
        startPositions.push_back(pattern.length() - currentSubPattern.length() + 1);
    }

    Trie trie;
    for (size_t i = 0; i < subPatterns.size(); ++i) {
        trie.addString(subPatterns[i], i);
    }

    /*for (const auto& it : subPatterns) {
        std::cout << it << ' ';
    }

    std::cout << '\n';

    for (const auto& it : startPositions) {
        std::cout << it << ' ';
    }

    std::cout << '\n';*/

    for (const auto& it : subPatterns) {
        patterns.push_back(it);
    }

    std::vector<std::pair<int, int>> results;
    trie.processText(text, results);

    std::vector<int> C(text.length(), 0);
    for (const auto& result : results) {
        int pos = result.first - startPositions[result.second - 1];
        if (pos >= 0 && pos + pattern.length() <= text.length()) {
            C[pos]++;
        }
    }

    std::vector<int> finalPositions;
    for (size_t i = 0; i < C.size(); ++i) {
        if (C[i] == subPatterns.size()) {
            finalPositions.push_back(i);
        }
    }

    return finalPositions;
}

int main() {
    std::string text;
    std::string pattern;
    char wildcard;

    std::cin >> text;
    std::cin >> pattern;
    std::cin >> wildcard;

    std::vector<int> positions = findPatternWithWildcards(text, pattern, wildcard);
    std::sort(positions.begin(), positions.end());
    for (int pos : positions) {
        std::cout << pos + 1 << "\n";
    }

    return 0;
}