Aho-Korasik_1

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

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

struct Node {
    /*std::array<Node*, N> son;
    std::array<Node*, N> go;*/
    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 = NULL;
        suffLink = NULL;
        up = NULL;
        charToParent = ' ';
        isTerminal = false;
        //leafPatternNumber = {0};
    }

} typedef Node;

struct Trie {
public:
    Node* root;

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

    Node* getSuffLink(Node* v) {
        //std::cout << "getSuffLink\n";
        if (v->suffLink == NULL) {
            if (v == root || v->parent == root) {
                v->suffLink = root;
            }
            else {
                v->suffLink = getLink(getSuffLink(v->parent), v->charToParent);
            }
        }
        //std::cout << "quit getSuffLink\n";
        return v->suffLink;
    }

    Node* getLink(Node* v, char c) {
        //std::cout << "getLink" << '\n';
        if (v->go[c] == NULL) {
            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);
            }
        }
        //std::cout << "quit getLink" << '\n';
        return v->go[c];
    }

    Node* getUp(Node* v) {
        //std::cout << "getUp\n";
        //std::cout << '\n';
        if (v->up == NULL) {
            if (getSuffLink(v)->isTerminal) {
                v->up = getSuffLink(v);
            }
            else if (getSuffLink(v) == root) {
                v->up = root;
            }
            else {
                v->up = getUp(getSuffLink(v));
            }
        }
        //std::cout << "quit getUp\n";
        return v->up;
    }

    void addString(std::string s, int patternNumber) {
        Node* curr = root;
        char c = ' ';
        for (size_t i = 0; i < s.length(); ++i) {
            c = s[i];
            if (curr->son[c] == NULL) {
                curr->son[c] = new Node();
                //curr->son[c]->suffLink = NULL;
                //curr->son[c]->up = NULL;
                curr->son[c]->parent = curr;
                curr->son[c]->charToParent = c;
                //curr->son[c]->isTerminal = false;
            }
            curr = curr->son[c];
            //std::cout << curr->charToParent << '\n';
        }
        //std::cout << c << '\n';
        curr->isTerminal = true;
        curr->leafPatternNumber.push_back(patternNumber);
    }

    void check(Node* v, int i) {
        Node* u = v;
        //std::cout << "check\n";
        while (u != root) {
            if (u->isTerminal) {
                //std::cout << i - patterns[u->leafPatternNumber[i]].length() + 1 << " " << patterns[u->leafPatternNumber[i]] << '\n';
            }
            u = getUp(u);
        }
        //std::cout << "quit check\n";
    }

    void find_all_pos(std::string& t) {
        Node* u = root;
        //std::cout << 1 << '\n';
        for (size_t i = 0; i < t.length(); ++i) {
            u = getLink(u, t[i]);
            Node* checkNode = u;
            check(checkNode, i + 1);
        }
    }

    void process_text(std::string& s, std::vector<std::pair<int, int>>& ans) {
        Node* curr = root;
        for (size_t i = 0; i < s.length(); ++i) {
            char c = s[i];
            curr = getLink(curr, c);
            Node* checkNode = curr;
            while (checkNode != root) {
                if(checkNode->isTerminal){
                    for (auto& patNum : checkNode->leafPatternNumber) {
                        //std::cout << i + 2 - patterns[patNum].length() << " " << patNum + 1 << '\n';
                        ans.push_back(std::make_pair(i + 2 - patterns[patNum].length(), patNum + 1));
                    }
                }
                checkNode = getUp(checkNode);
            }
        }
    }


    ~Trie() = default;

} typedef Trie;

int main() {
    Trie tr;
    //patterns = { "TAGT", "TAG", "T"};
    std::string t;
    std::cin >> t;
    int n;
    std::cin >> n;
    for (size_t i = 0; i < n; ++i) {
        std::string  str;
        std::cin >> str;
        patterns.push_back(str);
    }

    for (size_t i = 0; i < patterns.size(); ++i) {
        tr.addString(patterns[i], i);
    }
    std::vector<std::pair<int, int>> ans;
    tr.process_text(t, ans);
    std::sort(ans.begin(), ans.end());
    for (const auto& it : ans) {
        std::cout << it.first << ' ' << it.second << '\n';
    }
    return 0;
}