Seminar13

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>

struct Node {
  char Letter;  // Буква, по которой пришли в узел.
  bool IsTerminal = false;
  std::vector<Node*> Children;
  Node* Parent;
  Node* SuffLink = nullptr;

  Node(Node* parent, char letter) : Parent(parent), Letter(letter) {}
};

class Trie {
 public:
  Trie() : start(new Node(nullptr, 0)) { start->SuffLink = start; }
  ~Trie() {
    std::unordered_set<Node*> all;
    all.insert(start);
    std::queue<Node*> q;
    q.push(start);
    while (!q.empty()) {
      Node* cur = q.front(); q.pop();
      for (Node* c : cur->Children) {
        if (c != nullptr && !all.count(c)) {
          q.push(c);
          all.insert(c);
        }
      }
    }
    for (Node* x : all) delete x;
  }
  void Add(const std::string& s);
  void Print() const;
  void AhoCorasik(const std::string& text);

 private:
  Node* start;
  void DFSPrint(std::string& s, Node* current) const;
  Node* GoTo(Node* q, char a);
  Node* F(Node* q);
};

void Trie::AhoCorasik(const std::string& text) {
  Node* q = start;
  for (int i = 0; i < text.size(); ++i) {
    std::cout << i << "\n";
    q = GoTo(q, text[i]);
    // Выдать все терминальные, доступные по суфф.ссылкам.
    for (Node* x = q; x != start; x = F(x)) {
      if (x->IsTerminal) std::cout << "Found pattern with ending symbol " << x->Letter << "\n";
    }
  }
}
Node* Trie::GoTo(Node* q, char a) {
  if (q->Children.empty()) q->Children.assign(256, nullptr);
  if (q->Children[a]) return q->Children[a];
  if (!q->Parent) return q->Children[a] = q;
  return q->Children[a] = GoTo(F(q), a);
}
Node* Trie::F(Node* q) {
  if (q->SuffLink) return q->SuffLink;
  if (q->Parent == start) return q->SuffLink = start;
  return q->SuffLink = GoTo(F(q->Parent), q->Letter);
}
// hello
// hell
void Trie::Add(const std::string& s) {
  Node* cur_node = start;
  for (int i = 0; i < s.size(); ++i) {
    if (cur_node->Children.empty()) cur_node->Children.assign(256, nullptr);
    if (!cur_node->Children[s[i]]) {
      cur_node->Children[s[i]] = new Node(cur_node, s[i]);
    }
    cur_node = cur_node->Children[s[i]];
    cur_node->IsTerminal |= (i == s.size() - 1);
  }
}

void Trie::Print() const {
  std::string s;
  DFSPrint(s, start);
}

void Trie::DFSPrint(std::string& s, Node* current) const {
  if (current->IsTerminal) std::cout << s << "\n";
  for (int i = 0; i < current->Children.size(); ++i) {
    if (current->Children[i]) {
      s.push_back(char(i));
      DFSPrint(s, current->Children[i]);
      s.pop_back();
    }
  }
}

int main() {
  Trie trie;
  int n = 0; std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::string s;
    std::cin >> s;
    trie.Add(s);
  }
  trie.Print();
  std::string text; std::cin >> text;
  trie.AhoCorasik(text);
  return 0;
}