1 files changed, 45 insertions, 0 deletions
diff --git a/usth/MATH2.3/5/nfa.cc b/usth/MATH2.3/5/nfa.cc
new file mode 100644
index 0000000..8401202
--- /dev/null
+++ b/usth/MATH2.3/5/nfa.cc
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+using namespace std;
+
+bool
+recognize (unordered_map<int, unordered_map<int, vector<int>>>& f,
+           unordered_map<int, bool>& F, string& s, int i, int r)
+{
+  if (i >= s.size ())
+    return F[r];
+  for (auto const& t : f[r][s[i] - '0'])
+    if (recognize (f, F, s, i + 1, t))
+      return true;
+  return false;
+}
+
+int
+main ()
+{
+  int n;
+  unordered_map<int, unordered_map<int, vector<int>>> f;
+  cin >> n;
+  while (n--)
+    {
+      int s, i, r;
+      cin >> s >> i >> r;
+      f[s][i].push_back (r);
+    }
+
+  unordered_map<int, bool> F;
+  cin >> n;
+  while (n--)
+    {
+      int s;
+      cin >> s;
+      F[s] = true;
+    }
+
+  string s;
+  cin >> s;
+  cout << (recognize (f, F, s, 0, 0) ? "yes" : "no") << endl;
+}