ДКА

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;

struct transition {
  int s;
  int f;
  char c;

  transition(int _s, int _f, char _c) : s(_s), f(_f), c(_c) {}
  transition() = default;
  bool operator==(const transition &other) const {
    return s == other.s && f == other.f && c == other.c;
  }
};

class nFA {
private:
  vector<vector<int>> Q; // states - состояния // состаяния в векторе упорядочены по возрастанию
  vector<char> A; //конечный входной алфавит автомата;
  vector<transition> d; // transitions - переходы
  int q0;               //начальное сотсояние автомата
  vector<int> F;        //конечные состояния автомата

  int transit(int q, char ch) {
    int res = q;
    for (auto it = d.begin(); it != d.end(); it++) {
      if (it->s == q && it->c == ch)
        res = it->f;
    }
    return res;
  }

public:
  nFA(vector<vector<int>> _Q, vector<transition> _d, int _q0, vector<int> _F) : Q(_Q), d(_d), q0(_q0), F(_F) {
    set<char> s;
    for (auto it = d.begin(); it != d.end(); it++) {
      s.insert(it->c);
    }
    A = vector<char>(s.begin(), s.end());
  }

  ~nFA() {
    Q.clear();
    d.clear();
    F.clear();
    A.clear();
  }

  bool isDeterministic() {
    for (auto it = d.begin(); it != d.end(); it++) {
      for (auto et = d.begin(); et != d.end(); et++) {
        if (it->s == et->s && it->c == et->c && it->f != et->f)
          return false;
      }
    }
    return true;
  }

  vector<int> move(vector<int> state, char letter) {
    vector<int> res;
    set<int> v;
    for (auto it = state.begin(); it != state.end(); it++) {
      for (auto et = d.begin(); et != d.end(); et++) {
        if (et->s == *it && et->c == letter)
          v.insert(et->f);
      }
    }
    res = vector<int>(v.begin(), v.end());
    sort(res.begin(), res.end());
    return res;
  }

  bool isTerminal(vector<int> q) {
    for (auto state = q.begin(); state != q.end(); state++) {
      if (find(F.begin(), F.end(), *state) != F.end())
        return true;
    }
    return false;
  }

  bool isAccepting(string str) {
    int len = str.length();
    vector<int> q = {q0};
    for (int i = 0; i < len; i++) {
      q = move(q, str[i]);
    }
    return isTerminal(q);
  }

  nFA *determinize() {
    vector<vector<int>> Q1;
    vector<transition> d1;
    queue<vector<int>> Queue;

    vector<int> currStates;
    vector<int> newStates;

    Queue.push({q0});
    Q1.push_back({q0});

    while (!Queue.empty()) {
      currStates = Queue.front();
      Queue.pop();
      for (auto letter = A.begin(); letter != A.end(); letter++) {
        newStates.clear();
        newStates = move(currStates, *letter);
        if (newStates.size() != 0) {
          if (find(Q1.begin(), Q1.end(), newStates) == Q1.end()) {
            Q1.push_back(newStates);
            Queue.push(newStates);
          }

          vector<transition> newd;
          for (auto state = newStates.begin(); state != newStates.end(); state++) {
            for (auto it = d.begin(); it != d.end(); it++) {
              if (it->f == *state && it->c == *letter) {
                newd.push_back(transition(it->s, it->f, it->c));
              }
            }
          }
          for (auto it = newd.begin(); it != newd.end(); it++) {
            if (find(d1.begin(), d1.end(), *it) == d1.end()) {
              d1.push_back(*it);
            }
          }
        }
      }
    }

    return new nFA(Q1, d1, q0, F);
  }

  void print() {
    for (auto it = Q.begin(); it != Q.end(); it++) {
      cout << "<";
      for (auto state = it->begin(); state != it->end(); state++) {
        cout << *state << " ";
      }
      cout << ">" << endl;
    }
    cout << endl;
    cout << endl;
    for (auto it = d.begin(); it != d.end(); it++) {
      cout << it->s << " " << it->f << " " << it->c << endl;
    }
  }
};

int main() {
  ifstream ins("input.txt");
  ofstream outs("output.txt");

  int N; //количество состояний автомата
  int k; //номер начального состояния
  int f; //количество конечных состояний
  int p; //количество функций переходов
  int T; //количество строк, распознаваемость конечным автоматом которых
         //необходимо проверить

  ins >> N >> k >> f;

  vector<vector<int>> Q;
  for (int i = 0; i < N; i++) {
    Q.push_back({i});
  }

  vector<int> F;
  for (int i = 0; i < f; i++) {
    int q;
    ins >> q;
    F.push_back(q);
  }

  ins >> p;
  vector<transition> d;
  for (int i = 0; i < p; i++) {
    transition t;
    ins >> t.s >> t.f >> t.c;
    d.push_back(t);
  }

  nFA *ka = new nFA(Q, d, k, F);

  if (!ka->isDeterministic()) {
    nFA *nka = ka->determinize();
    delete ka;
    ka = nka;
  }

  ins >> T;
  for (int i = 0; i < T; i++) {
    string str;
    ins >> str;
    if (ka->isAccepting(str))
      outs << "YES" << endl;
    else
      outs << "NO" << endl;
  }

  delete ka;
  ins.close();
  outs.close();
  return 0;
}