Algorithms : add 04-algorithms_on_strings 04-suffix_array

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