From 7471f538c2203f266cb8002fb001183a9720a969 Mon Sep 17 00:00:00 2001
From: Jérémy Zurcher <jeremy@asynk.ch>
Date: Mon, 14 Nov 2016 07:00:58 +0100
Subject: Algorithms : add 04-algorithms_on_strings 04-suffix_array

---
 .../04-suffix_array/01-kmp/kmp.cpp                 | 29 ++++++++++++++++++++++
 .../04-suffix_array/01-kmp/tests/sample1           |  2 ++
 .../04-suffix_array/01-kmp/tests/sample1.a         |  1 +
 .../04-suffix_array/01-kmp/tests/sample2           |  2 ++
 .../04-suffix_array/01-kmp/tests/sample2.a         |  1 +
 .../04-suffix_array/01-kmp/tests/sample3           |  2 ++
 .../04-suffix_array/01-kmp/tests/sample3.a         |  1 +
 7 files changed, 38 insertions(+)
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample1.a
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample2.a
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3
 create mode 100644 04-algorithms_on_strings/04-suffix_array/01-kmp/tests/sample3.a

(limited to '04-algorithms_on_strings/04-suffix_array/01-kmp')

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