From 45188449a04a1455ade01caf470e43a926d752aa Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Mon, 14 Nov 2016 06:35:05 +0100 Subject: Algorithms : add 04-algorithms_on_strings 01-suffix_trees --- .../01-suffix_trees/02-trie_matching/tests/sample1 | 3 + .../02-trie_matching/tests/sample1.a | 1 + .../01-suffix_trees/02-trie_matching/tests/sample2 | 3 + .../02-trie_matching/tests/sample2.a | 0 .../01-suffix_trees/02-trie_matching/tests/sample3 | 4 ++ .../02-trie_matching/tests/sample3.a | 1 + .../02-trie_matching/trie_matching.cpp | 80 ++++++++++++++++++++++ 7 files changed, 92 insertions(+) create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1 create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample1.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2 create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample2.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3 create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/tests/sample3.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/02-trie_matching/trie_matching.cpp (limited to '04-algorithms_on_strings/01-suffix_trees/02-trie_matching') 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 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 +#include +#include +#include +#include +#include + +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 solve (const string& text, int n, const vector & patterns) +{ + vector result; + + // write your code here + + return result; +} + +int main (void) +{ + string t; + cin >> t; + + int n; + cin >> n; + + vector patterns (n); + for (int i = 0; i < n; i++) + { + cin >> patterns[i]; + } + + vector 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; +} -- cgit v1.2.3