diff options
Diffstat (limited to '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 Binary files differnew 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 + |