diff options
Diffstat (limited to '02-data_structures/03-hash_tables/03-hash_substring')
7 files changed, 47 insertions, 0 deletions
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp b/02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp new file mode 100644 index 0000000..3a3680a --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp @@ -0,0 +1,38 @@ +#include <iostream> +#include <string> +#include <vector> + +using std::string; +typedef unsigned long long ull; + +struct Data { + string pattern, text; +}; + +Data read_input() { + Data data; + std::cin >> data.pattern >> data.text; + return data; +} + +void print_occurrences(const std::vector<int>& output) { + for (size_t i = 0; i < output.size(); ++i) + std::cout << output[i] << " "; + std::cout << "\n"; +} + +std::vector<int> get_occurrences(const Data& input) { + const string& s = input.pattern, t = input.text; + std::vector<int> ans; + for (size_t i = 0; i + s.size() <= t.size(); ++i) + if (t.substr(i, s.size()) == s) + ans.push_back(i); + return ans; +} + + +int main() { + std::ios_base::sync_with_stdio(false); + print_occurrences(get_occurrences(read_input())); + return 0; +} diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/01 b/02-data_structures/03-hash_tables/03-hash_substring/tests/01 new file mode 100644 index 0000000..88aa221 --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/01 @@ -0,0 +1,2 @@ +aba +abacaba diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/01.a b/02-data_structures/03-hash_tables/03-hash_substring/tests/01.a new file mode 100644 index 0000000..45d56c5 --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/01.a @@ -0,0 +1 @@ +0 4 diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/02 b/02-data_structures/03-hash_tables/03-hash_substring/tests/02 new file mode 100644 index 0000000..4ca249f --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/02 @@ -0,0 +1,2 @@ +Test +testTesttesT diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/02.a b/02-data_structures/03-hash_tables/03-hash_substring/tests/02.a new file mode 100644 index 0000000..8adb55b --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/02.a @@ -0,0 +1 @@ +4 diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/03 b/02-data_structures/03-hash_tables/03-hash_substring/tests/03 new file mode 100644 index 0000000..4977bbb --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/03 @@ -0,0 +1,2 @@ +aaaaa +baaaaaaa diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/03.a b/02-data_structures/03-hash_tables/03-hash_substring/tests/03.a new file mode 100644 index 0000000..46786e9 --- /dev/null +++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/03.a @@ -0,0 +1 @@ +1 2 3 |