Slight changes to suffix tree and adding implicit cartesian STL tree.

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; }	
 };
diff --git a/tcr.pdf b/tcr.pdf
index 544f37a..25cb245 100644
--- a/tcr.pdf
+++ b/tcr.pdf