diff options
| -rw-r--r-- | datastructures/datastructures.tex | 3 | ||||
| -rw-r--r-- | datastructures/stlRope.cpp | 8 | ||||
| -rw-r--r-- | string/suffixTree.cpp | 27 | ||||
| -rw-r--r-- | string/trie.cpp | 2 | ||||
| -rw-r--r-- | tcr.pdf | bin | 295781 -> 295819 bytes |
5 files changed, 25 insertions, 15 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4267090..9018cd5 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -17,3 +17,6 @@ Dazu: Offset in den inneren Knoten des Baums speichern. \subsection{STL-Tree} \lstinputlisting{datastructures/stlTree.cpp} + +\subsection{STL-Rope} +\lstinputlisting{datastructures/stlRope.cpp} diff --git a/datastructures/stlRope.cpp b/datastructures/stlRope.cpp new file mode 100644 index 0000000..9179a60 --- /dev/null +++ b/datastructures/stlRope.cpp @@ -0,0 +1,8 @@ +#include <ext/rope> +using namespace __gnu_cxx; +rope<int> v; // Wie normaler Container. +v.push_back(num); // O(log(n)) +rope<int> sub = v.substr(start, length); // O(log(n)) +v.erase(start, length); // O(log(n)) +v.insert(v.mutable_begin() + offset, sub); // O(log(n)) +for(auto it = v.mutable_begin(); it != v.mutable_end(); it++) {...} diff --git a/string/suffixTree.cpp b/string/suffixTree.cpp index fba8e16..fe065b2 100644 --- a/string/suffixTree.cpp +++ b/string/suffixTree.cpp @@ -1,21 +1,20 @@ // Baut Suffixbaum online auf. Laufzeit: O(n) // Einmal initSuffixTree() aufrufen und dann extend für jeden Buchstaben. -// $-Zeichen (oder ähnliches) an den Text anhängen! -static const int ALPHABET_SIZE = 128, INF = 0x3FFFFFFF; +// '\0'-Zeichen (oder ähnliches) an den Text anhängen! string s; int root, lastIdx, needsSuffix, pos, remainder, curVert, curEdge, curLen; struct Vert { - int start, end, suffix, next[ALPHABET_SIZE]; + int start, end, suffix; // Kante [start,end) + map<char, int> next; int len() { return min(end, pos + 1) - start; } }; vector<Vert> tree; -int newVert(int start, int end = INF) { +int newVert(int start, int end) { Vert v; v.start = start; v.end = end; v.suffix = 0; - memset(v.next, 0, sizeof(v.next)); tree.push_back(v); return ++lastIdx; } @@ -47,13 +46,13 @@ void extend() { remainder++; while (remainder) { if (curLen == 0) curEdge = pos; - if (tree[curVert].next[(int)s[curEdge]] == 0) { - int leaf = newVert(pos); - tree[curVert].next[(int)s[curEdge]] = leaf; - tree[curVert].next[(int)s[curEdge]] = leaf; + if (!tree[curVert].next.count(s[curEdge])) { + int leaf = newVert(pos, s.size()); + tree[curVert].next[s[curEdge]] = leaf; + tree[curVert].next[s[curEdge]] = leaf; addSuffixLink(curVert); } else { - int nxt = tree[curVert].next[(int)s[curEdge]]; + int nxt = tree[curVert].next[s[curEdge]]; if (fullImplicitEdge(nxt)) continue; if (s[tree[nxt].start + curLen] == s[pos]) { curLen++; @@ -61,11 +60,11 @@ void extend() { break; } int split = newVert(tree[nxt].start, tree[nxt].start + curLen); - tree[curVert].next[(int)s[curEdge]] = split; - int leaf = newVert(pos); - tree[split].next[(int)s[pos]] = leaf; + tree[curVert].next[s[curEdge]] = split; + int leaf = newVert(pos, s.size()); + tree[split].next[s[pos]] = leaf; tree[nxt].start += curLen; - tree[split].next[(int)s[tree[nxt].start]] = nxt; + tree[split].next[s[tree[nxt].start]] = nxt; addSuffixLink(split); } remainder--; diff --git a/string/trie.cpp b/string/trie.cpp index 163a110..1b5f573 100644 --- a/string/trie.cpp +++ b/string/trie.cpp @@ -1,5 +1,5 @@ struct node { - node *(e)[26]; // Implementierung für Kleinbuchstaben. + 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; } }; Binary files differ |