diff options
| -rw-r--r-- | string/ahoCorasick.cpp | 10 | ||||
| -rw-r--r-- | string/kmp.cpp | 10 | ||||
| -rw-r--r-- | string/levenshtein.cpp | 13 | ||||
| -rw-r--r-- | string/longestCommonSubsequence.cpp (renamed from string/LCSubSequence.cpp) | 4 | ||||
| -rw-r--r-- | string/string.tex | 5 | ||||
| -rw-r--r-- | string/trie.cpp | 6 | ||||
| -rw-r--r-- | tcr.pdf | bin | 256267 -> 253834 bytes |
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; Binary files differ |