diff options
Diffstat (limited to '04-algorithms_on_strings/04-suffix_array/01-kmp')
7 files changed, 38 insertions, 0 deletions
diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp b/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp new file mode 100644 index 0000000..13121ae --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp @@ -0,0 +1,29 @@ +#include <cstdio> +#include <iostream> +#include <string> +#include <vector> + +using std::cin; +using std::string; +using std::vector; + +// Find all occurrences of the pattern in the text and return a +// vector with all positions in the text (starting from 0) where +// the pattern starts in the text. +vector<int> find_pattern(const string& pattern, const string& text) { + vector<int> result; + // Implement this function yourself + return result; +} + +int main() { + string pattern, text; + cin >> pattern; + cin >> text; + vector<int> result = find_pattern(pattern, text); + for (int i = 0; i < result.size(); ++i) { + printf("%d ", result[i]); + } + printf("\n"); + return 0; +} diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1 b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1 new file mode 100644 index 0000000..66fbc8f --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1 @@ -0,0 +1,2 @@ +TACG +GT diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1.a b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1.a new file mode 100644 index 0000000..8b13789 --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1.a @@ -0,0 +1 @@ + diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2 b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2 new file mode 100644 index 0000000..636224a --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2 @@ -0,0 +1,2 @@ +ATA +ATATA diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2.a b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2.a new file mode 100644 index 0000000..fa581ef --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2.a @@ -0,0 +1 @@ +0 2 diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3 b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3 new file mode 100644 index 0000000..0a08309 --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3 @@ -0,0 +1,2 @@ +ATAT +GATATATGCATATACTT diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3.a b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3.a new file mode 100644 index 0000000..5ac4cba --- /dev/null +++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3.a @@ -0,0 +1 @@ +1 3 9 |