merge pdf

3 files changed, 15 insertions, 5 deletions

diff --git a/string/kmp.cpp b/string/kmp.cpp
index f7c3630..6844975 100644
--- a/string/kmp.cpp
+++ b/string/kmp.cpp
@@ -1,8 +1,3 @@
-#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);
diff --git a/string/levenshtein.cpp b/string/levenshtein.cpp
new file mode 100644
index 0000000..d1980f8
--- /dev/null
+++ b/string/levenshtein.cpp
@@ -0,0 +1,12 @@
+int levenshtein(string& s1, string& s2) {
+	int len1 = s1.size(), len2 = s2.size();
+	vector<int> col(len2 + 1), prevCol(len2 + 1);
+	for (int i = 0; i < len2 + 1; i++) prevCol[i] = i;
+	for (int i = 0; i < len1; i++) {
+		col[0] = i + 1;
+		for (int j = 0; j < len2; j++)
+			col[j+1] = min(min(prevCol[j+1] + 1, col[j] + 1), prevCol[j] + (s1[i]==s2[j] ? 0 : 1));
+		col.swap(prevCol);
+	}
+	return prevCol[len2];
+}
\ No newline at end of file
diff --git a/string/string.tex b/string/string.tex
index 61385fc..0fddb86 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -3,6 +3,9 @@
 \subsection{\textsc{Knuth-Morris-Pratt}-Algorithmus}
 \lstinputlisting{string/kmp.cpp}
 
+\subsection{\textsc{Levenshtein}-Distanz}
+\lstinputlisting{string/levenshtein.cpp}
+
 \subsection{Trie}
 \lstinputlisting{string/trie.cpp}