From b2859449d6facd0c78f59fd2ce6fdf651b4c8970 Mon Sep 17 00:00:00 2001
From: kittobi1992 <kittobi1992@users.noreply.github.com>
Date: Sat, 22 Nov 2014 11:48:12 +0100
Subject: Update kmp.cpp

Adding KMP-Search (Search after a Substring in a String)
---
 string/kmp.cpp | 36 +++++++++++++++++++++++++++++++++++-
 1 file changed, 35 insertions(+), 1 deletion(-)

(limited to 'string')

diff --git a/string/kmp.cpp b/string/kmp.cpp
index 7898192..f7c3630 100644
--- a/string/kmp.cpp
+++ b/string/kmp.cpp
@@ -1 +1,35 @@
-a
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+//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;
+}
+
+//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;
+}
-- 
cgit v1.2.3