Typesetting string section.

7 files changed, 15 insertions, 33 deletions

diff --git a/string/ahoCorasick.cpp b/string/ahoCorasick.cpp
index 1f604c2..c283f6f 100644
--- a/string/ahoCorasick.cpp
+++ b/string/ahoCorasick.cpp
@@ -1,11 +1,13 @@
-// Laufzeit: O(n + m + z), n = Suchstringlänge, m = Summe der Patternlängen, z = #Matches
+// Laufzeit: O(n + m + z), n = #Text, m = Summe #Pattern, z = #Matches
 // Findet mehrere Patterns gleichzeitig in einem String.
 // 1) Wurzel erstellen: vertex *automaton = new vertex();
 // 2) Mit addString(automaton, s, idx); Patterns hinzufügen.
 // 3) finishAutomaton(automaton) aufrufen.
-// 4) Mit automaton = go(automaton, c) in nächsten Zustand wechseln. DANACH: Wenn patterns-Vektor nicht leer
-//    ist: Hier enden alle enthaltenen Patterns.
-// ACHTUNG: Die Zahlenwerte der auftretenden Buchstaben müssen zusammenhängend sein und bei 0 beginnen!
+// 4) Mit automaton = go(automaton, c) in nächsten Zustand wechseln.
+//    DANACH: Wenn patterns-Vektor nicht leer ist: Hier enden alle
+//    enthaltenen Patterns.
+// ACHTUNG: Die Zahlenwerte der auftretenden Buchstaben müssen
+// zusammenhängend sein und bei 0 beginnen!
 struct vertex {
   vertex *next[ALPHABET_SIZE], *failure;
   char character; 
diff --git a/string/kmp.cpp b/string/kmp.cpp
index 47feac5..450b368 100644
--- a/string/kmp.cpp
+++ b/string/kmp.cpp
@@ -1,5 +1,5 @@
 // Laufzeit: O(n + m), n = #Text, m = #Pattern
-vector<int> kmp_preprocessing(string &sub) {
+vector<int> kmpPreprocessing(string &sub) {
   vector<int> b(sub.length() + 1);
   b[0] = -1;
   int i = 0, j = -1;
@@ -11,9 +11,8 @@ vector<int> kmp_preprocessing(string &sub) {
   return b;
 }
 
-vector<int> kmp_search(string &s, string &sub) {
-  vector<int> pre = kmp_preprocessing(sub);
-  vector<int> result;
+vector<int> kmpSearch(string &s, string &sub) {
+  vector<int> pre = kmpPreprocessing(sub), result;
   int i = 0, j = 0;
   while (i < (int)s.length()) {
     while (j >= 0 && s[i] != sub[j]) j = pre[j];
@@ -21,7 +20,6 @@ vector<int> kmp_search(string &s, string &sub) {
     if (j == (int)sub.length()) {
       result.push_back(i - j);
       j = pre[j];
-    }
-  }
+  }}
   return result;
 }
diff --git a/string/levenshtein.cpp b/string/levenshtein.cpp
deleted file mode 100644
index f0df66b..0000000
--- a/string/levenshtein.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-// Laufzeit: O(nm), Speicher: O(m), n = #s1, m = #s2
-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];
-}
diff --git a/string/LCSubSequence.cpp b/string/longestCommonSubsequence.cpp
index 0ea2913..7bcf851 100644
--- a/string/LCSubSequence.cpp
+++ b/string/longestCommonSubsequence.cpp
@@ -1,3 +1,4 @@
+// Laufzeit: O(|a|*|b|)
 string lcss(string &a, string &b) {
 	int m[a.length() + 1][b.length() + 1], x=0, y=0;
 	memset(m, 0, sizeof(m));
@@ -5,8 +6,7 @@ string lcss(string &a, string &b) {
 		for(int x = b.length() - 1; x >= 0; x--) {
 			if(a[y] == b[x]) m[y][x] = 1 + m[y+1][x+1];
 			else m[y][x] = max(m[y+1][x], m[y][x+1]);
-		}
-	} //for length only: return m[0][0];
+	}} // Für die Länge: return m[0][0];
 	string res;
 	while(x < b.length() && y < a.length()) {
 		if(a[y] == b[x]) res += a[y++], x++;
diff --git a/string/string.tex b/string/string.tex
index d4180c6..16ad30a 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -6,9 +6,6 @@
 \subsection{\textsc{Aho-Corasick}-Automat}
 \lstinputlisting{string/ahoCorasick.cpp}
 
-\subsection{\textsc{Levenshtein}-Distanz}
-\lstinputlisting{string/levenshtein.cpp}
-
 \subsection{Trie}
 \lstinputlisting{string/trie.cpp}
 
@@ -19,4 +16,4 @@
 \lstinputlisting{string/LCSubstring.cpp}
 
 \subsection{Longest Common Subsequence}
-\lstinputlisting{string/LCSubSequence.cpp}
+\lstinputlisting{string/longestCommonSubsequence.cpp}
diff --git a/string/trie.cpp b/string/trie.cpp
index 5ee7a87..33889dc 100644
--- a/string/trie.cpp
+++ b/string/trie.cpp
@@ -1,6 +1,5 @@
-// Implementierung für Kleinbuchstaben.
 struct node {
-	node *(e)[26];
+	node *(e)[26]; // Implementierung für Kleinbuchstaben.
 	int c = 0; // Anzahl der Wörter, die an diesem node enden.
 	node() { for(int i = 0; i < 26; i++) e[i] = NULL; }	
 };
@@ -11,8 +10,7 @@ void insert(node *root, string &txt, int s) { // Laufzeit: O(|txt|)
 		int idx = (int)(txt[s] - 'a');
 		if(root->e[idx] == NULL) root->e[idx] = new node();
 		insert(root->e[idx], txt, s+1);
-	}
-}
+}}
 
 int contains(node *root, string &txt, int s) { // Laufzeit: O(|txt|)
 	if(s == txt.size()) return root->c;
diff --git a/tcr.pdf b/tcr.pdf
index a858ecc..42d6f23 100644
--- a/tcr.pdf
+++ b/tcr.pdf