Algorithms : add 04-algorithms_on_strings 01-suffix_trees

7 files changed, 92 insertions, 0 deletions

diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1
new file mode 100644
index 0000000..0febb82
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1
@@ -0,0 +1,3 @@
+AAA
+1
+AA
diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1.a
new file mode 100644
index 0000000..6e8183b
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1.a
@@ -0,0 +1 @@
+0 1
diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2
new file mode 100644
index 0000000..5b50e43
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2
@@ -0,0 +1,3 @@
+AA
+1
+T
diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2.a
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2.a
diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3 b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3
new file mode 100644
index 0000000..cfabba3
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3
@@ -0,0 +1,4 @@
+AATCGGGTTCAATCGGGGT
+2
+ATCG
+GGGT
diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3.a b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3.a
new file mode 100644
index 0000000..d2ec362
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3.a
@@ -0,0 +1 @@
+1 4 11 15
diff --git a/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/trie_matching.cpp b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/trie_matching.cpp
new file mode 100644
index 0000000..a59a0db
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/02-trie_matching/trie_matching.cpp
@@ -0,0 +1,80 @@
+#include <algorithm>
+#include <cassert>
+#include <cstdio>
+#include <iostream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+int const Letters =    4;
+int const NA      =   -1;
+
+struct Node
+{
+	int next [Letters];
+
+	Node ()
+	{
+		fill (next, next + Letters, NA);
+	}
+
+	bool isLeaf () const
+	{
+	    return (next[0] == NA && next[1] == NA && next[2] == NA && next[3] == NA);
+	}
+};
+
+int letterToIndex (char letter)
+{
+	switch (letter)
+	{
+		case 'A': return 0; break;
+		case 'C': return 1; break;
+		case 'G': return 2; break;
+		case 'T': return 3; break;
+		default: assert (false); return -1;
+	}
+}
+
+vector <int> solve (const string& text, int n, const vector <string>& patterns)
+{
+	vector <int> result;
+
+	// write your code here
+
+	return result;
+}
+
+int main (void)
+{
+	string t;
+	cin >> t;
+
+	int n;
+	cin >> n;
+
+	vector <string> patterns (n);
+	for (int i = 0; i < n; i++)
+	{
+		cin >> patterns[i];
+	}
+
+	vector <int> ans;
+	ans = solve (t, n, patterns);
+
+	for (int i = 0; i < (int) ans.size (); i++)
+	{
+		cout << ans[i];
+		if (i + 1 < (int) ans.size ())
+		{
+			cout << " ";
+		}
+		else
+		{
+			cout << endl;
+		}
+	}
+
+	return 0;
+}