Algorithms : add 04-algorithms_on_strings 01-suffix_trees

37 files changed, 369 insertions, 0 deletions

diff --git a/04-algorithms_on_strings/01-suffix_trees/00_suffix-trees.pdf b/04-algorithms_on_strings/01-suffix_trees/00_suffix-trees.pdf
new file mode 100644
index 0000000..c02b2f8
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/00_suffix-trees.pdf
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1
new file mode 100644
index 0000000..15cc060
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1
@@ -0,0 +1,2 @@
+1
+ATA
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a
new file mode 100644
index 0000000..99ce28c
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a
@@ -0,0 +1,3 @@
+0->1:A
+1->2:T
+2->3:A
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2
new file mode 100644
index 0000000..509298a
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2
@@ -0,0 +1,4 @@
+3
+AT
+AG
+AC
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a
new file mode 100644
index 0000000..e9b94b5
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a
@@ -0,0 +1,4 @@
+0->1:A
+1->4:C
+1->3:G
+1->2:T
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3 b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3
new file mode 100644
index 0000000..b454c19
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3
@@ -0,0 +1,4 @@
+3
+ATAGA
+ATC
+GAT
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a
new file mode 100644
index 0000000..b789e0f
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a
@@ -0,0 +1,9 @@
+0->1:A
+0->7:G
+1->2:T
+2->3:A
+2->6:C
+3->4:G
+4->5:A
+7->8:A
+8->9:T
diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp b/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp
new file mode 100644
index 0000000..08cfe9b
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp
@@ -0,0 +1,37 @@
+#include <string>
+#include <iostream>
+#include <vector>
+#include <map>
+
+using std::map;
+using std::vector;
+using std::string;
+
+typedef map<char, int> edges;
+typedef vector<edges> trie;
+
+trie build_trie(vector<string> & patterns) {
+  trie t;
+  // write your code here
+  return t;
+}
+
+int main() {
+  size_t n;
+  std::cin >> n;
+  vector<string> patterns;
+  for (size_t i = 0; i < n; i++) {
+    string s;
+    std::cin >> s;
+    patterns.push_back(s);
+  }
+
+  trie t = build_trie(patterns);
+  for (size_t i = 0; i < t.size(); ++i) {
+    for (const auto & j : t[i]) {
+      std::cout << i << "->" << j.second << ":" << j.first << "\n";
+    }
+  }
+
+  return 0;
+}
\ No newline at end of file
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;
+}
diff --git a/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample1
new file mode 100644
index 0000000..0febb82
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample1
@@ -0,0 +1,3 @@
+AAA
+1
+AA
diff --git a/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample1.a
new file mode 100644
index 0000000..6e8183b
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample1.a
@@ -0,0 +1 @@
+0 1
diff --git a/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample2
new file mode 100644
index 0000000..0f04d22
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample2
@@ -0,0 +1,5 @@
+ACATA
+3
+AT
+A
+AG
diff --git a/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample2.a
new file mode 100644
index 0000000..e90dcac
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/tests/sample2.a
@@ -0,0 +1 @@
+0 2 4
diff --git a/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/trie_matching_extended.cpp b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/trie_matching_extended.cpp
new file mode 100644
index 0000000..c68c2f6
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/03-trie_matching_extended/trie_matching_extended.cpp
@@ -0,0 +1,77 @@
+#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];
+	bool patternEnd;
+
+	Node ()
+	{
+		fill (next, next + Letters, NA);
+		patternEnd = false;
+	}
+};
+
+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 (string text, int n, 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;
+}
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp
new file mode 100644
index 0000000..5d9e2f1
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp
@@ -0,0 +1,30 @@
+#include <iostream>
+#include <map>
+#include <string>
+#include <vector>
+
+using std::cin;
+using std::cout;
+using std::endl;
+using std::map;
+using std::string;
+using std::vector;
+
+// Build a suffix tree of the string text and return a vector
+// with all of the labels of its edges (the corresponding 
+// substrings of the text) in any order.
+vector<string> ComputeSuffixTreeEdges(const string& text) {
+  vector<string> result;
+  // Implement this function yourself
+  return result;
+}
+
+int main() {
+  string text;
+  cin >> text;
+  vector<string> edges = ComputeSuffixTreeEdges(text);
+  for (int i = 0; i < edges.size(); ++i) {
+    cout << edges[i] << endl;
+  }
+  return 0;
+}
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1
new file mode 100644
index 0000000..09574e8
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1
@@ -0,0 +1 @@
+A$
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a
new file mode 100644
index 0000000..29f8526
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a
@@ -0,0 +1,2 @@
+$
+A$
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2
new file mode 100644
index 0000000..e73cda6
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2
@@ -0,0 +1 @@
+ACA$
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a
new file mode 100644
index 0000000..e374793
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a
@@ -0,0 +1,5 @@
+$
+CA$
+A
+$
+CA$
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3 b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3
new file mode 100644
index 0000000..cd7fdc4
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3
@@ -0,0 +1 @@
+ATAAATG$
diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a
new file mode 100644
index 0000000..2a60baa
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a
@@ -0,0 +1,12 @@
+$
+T
+G$
+AAATG$
+G$
+A
+T
+G$
+AAATG$
+A
+TG$
+ATG$
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/non_shared_substring.cpp b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/non_shared_substring.cpp
new file mode 100644
index 0000000..2f2d98f
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/non_shared_substring.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <string>
+
+using namespace std;
+
+string solve (string p, string q)
+{
+	string result = p;
+
+	return result;
+}
+
+int main (void)
+{
+	string p;
+	cin >> p;
+	string q;
+	cin >> q;
+
+	string ans = solve (p, q);
+
+	cout << ans << endl;
+
+	return 0;
+}
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample1
new file mode 100644
index 0000000..34d4439
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample1
@@ -0,0 +1,2 @@
+A
+T
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample1.a
new file mode 100644
index 0000000..f70f10e
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample1.a
@@ -0,0 +1 @@
+A
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample2
new file mode 100644
index 0000000..40e933d
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample2
@@ -0,0 +1,2 @@
+AAAAAAAAAAAAAAAAAAAA
+TTTTTTTTTTTTTTTTTTTT
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample2.a
new file mode 100644
index 0000000..f70f10e
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample2.a
@@ -0,0 +1 @@
+A
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample3 b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample3
new file mode 100644
index 0000000..8ef5339
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample3
@@ -0,0 +1,2 @@
+CCAAGCTGCTAGAGG
+CATGCTGGGCTGGCT
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample3.a b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample3.a
new file mode 100644
index 0000000..36ff5de
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample3.a
@@ -0,0 +1 @@
+CC
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample4 b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample4
new file mode 100644
index 0000000..97910a5
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample4
@@ -0,0 +1,2 @@
+ATGCGATGACCTGACTGA
+CTCAACGTATTGGCCAGA
diff --git a/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample4.a b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample4.a
new file mode 100644
index 0000000..3711192
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/05-non_shared_substring/tests/sample4.a
@@ -0,0 +1 @@
+TGC
diff --git a/04-algorithms_on_strings/01-suffix_trees/check b/04-algorithms_on_strings/01-suffix_trees/check
new file mode 100755
index 0000000..b73ff99
--- /dev/null
+++ b/04-algorithms_on_strings/01-suffix_trees/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
+