From a3dd2581ed4847670f81157091016c14ca18803d Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Tue, 14 Jan 2020 18:29:11 +0700
Subject: [usth/MATH2.3] Mathemate Discretely

---
 usth/MATH2.3/5/nfa.cc | 45 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
 create mode 100644 usth/MATH2.3/5/nfa.cc

(limited to 'usth/MATH2.3/5/nfa.cc')

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;
+}
-- 
cgit 1.4.1