From e6b725d69c07d4a582d0aadc915def99d872dfde Mon Sep 17 00:00:00 2001
From: Jérémy Zurcher <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 22:22:32 +0100
Subject: Algorithms : add 02-data_structures 03-hash_tables

---
 .../03-hash_substring/hash_substring.cpp           | 38 ++++++++++++++++++++++
 .../03-hash_tables/03-hash_substring/tests/01      |  2 ++
 .../03-hash_tables/03-hash_substring/tests/01.a    |  1 +
 .../03-hash_tables/03-hash_substring/tests/02      |  2 ++
 .../03-hash_tables/03-hash_substring/tests/02.a    |  1 +
 .../03-hash_tables/03-hash_substring/tests/03      |  2 ++
 .../03-hash_tables/03-hash_substring/tests/03.a    |  1 +
 7 files changed, 47 insertions(+)
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/tests/01
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/tests/01.a
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/tests/02
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/tests/02.a
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/tests/03
 create mode 100644 02-data_structures/03-hash_tables/03-hash_substring/tests/03.a

(limited to '02-data_structures/03-hash_tables/03-hash_substring')

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 
-- 
cgit v1.2.3