Algorithms : add 02-data_structures 03-hash_tables

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