From 86978d60f8d2148362119fdccf680320a50dcc1f Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sun, 24 Apr 2016 10:46:02 +0200
Subject: Adding 3D spheres and some small changes to KMP.

---
 string/kmp.cpp | 51 ++++++++++++++++++++++++---------------------------
 1 file changed, 24 insertions(+), 27 deletions(-)

(limited to 'string')

diff --git a/string/kmp.cpp b/string/kmp.cpp
index 6844975..47feac5 100644
--- a/string/kmp.cpp
+++ b/string/kmp.cpp
@@ -1,30 +1,27 @@
-//Preprocessing Substring sub for KMP-Search
-vector<int> kmp_preprocessing(string& sub) {
-	vector<int> b(sub.size() + 1);
-	b[0] = -1;
-	int i = 0, j = -1;
-	while(i < sub.size()) {
-		while(j >= 0 && sub[i] != sub[j])
-			j = b[j];
-		i++; j++;
-		b[i] = j;
-	}
-	return b;
+// Laufzeit: O(n + m), n = #Text, m = #Pattern
+vector<int> kmp_preprocessing(string &sub) {
+  vector<int> b(sub.length() + 1);
+  b[0] = -1;
+  int i = 0, j = -1;
+  while (i < (int)sub.length()) {
+    while (j >= 0 && sub[i] != sub[j]) j = b[j];
+    i++; j++;
+    b[i] = j;
+  }
+  return b;
 }
 
-//Searching after Substring sub in s
-vector<int> kmp_search(string& s, string& sub) {
-	vector<int> pre = kmp_preprocessing(sub);
-	vector<int> result;
-	int i = 0, j = -1;
-	while(i < s.size()) {
-		while(j >= 0 && s[i] != sub[j])
-			j = pre[j];
-		i++; j++;
-		if(j == sub.size()) {
-			result.push_back(i-j);
-			j = pre[j];
-		}
-	}
-	return result;
+vector<int> kmp_search(string &s, string &sub) {
+  vector<int> pre = kmp_preprocessing(sub);
+  vector<int> result;
+  int i = 0, j = 0;
+  while (i < (int)s.length()) {
+    while (j >= 0 && s[i] != sub[j]) j = pre[j];
+    i++; j++;
+    if (j == (int)sub.length()) {
+      result.push_back(i - j);
+      j = pre[j];
+    }
+  }
+  return result;
 }
-- 
cgit v1.2.3