23 files changed, 505 insertions, 5 deletions

diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
new file mode 100644
index 0000000..899db15
--- /dev/null
+++ b/datastructures/RMQ.cpp
@@ -0,0 +1,20 @@
+vector<int> data(RMQ_SIZE);
+vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE));
+
+void initRMQ() {
+	for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) {
+		for(int l = 0; l + s <= RMQ_SIZE; l++) {
+			if(i == 0) rmq[0][l] = l;
+			else {
+				int r = l + ss;
+				rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]);
+			}
+		}
+	}
+}
+//returns index of minimum! [a, b)
+int queryRMQ(int l, int r) {
+	if(l >= r) return l;
+	int s = floor(log2(r-l)); r = r - (1 << s);
+	return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]);
+}
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index c314400..baa4fec 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -5,3 +5,6 @@
 
 \subsection{Segmentbaum}
 \lstinputlisting{datastructures/segmentTree.cpp}
+
+\subsection{Range Minimum Query}
+\lstinputlisting{datastructures/RMQ.cpp}
diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp
new file mode 100644
index 0000000..5d6bc16
--- /dev/null
+++ b/geometry/convexHull.cpp
@@ -0,0 +1,49 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+using namespace std;
+
+struct point {
+  double x, y;
+  point(){} point(double x, double y) : x(x), y(y) {}
+  bool operator <(const point &p) const {
+    return x < p.x || (x == p.x && y < p.y);
+  }
+};
+ 
+// 2D cross product.
+// Return a positive value, if OAB makes a counter-clockwise turn,
+// negative for clockwise turn, and zero if the points are collinear.
+double cross(const point &O, const point &A, const point &B){
+  double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
+  if (fabs(d) < 1e-9) return 0.0;
+  return d;
+}
+ 
+// Returns a list of points on the convex hull in counter-clockwise order.
+// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test
+// Note: the last point in the returned list is the same as the first one.
+vector<point> convexHull(vector<point> P){
+  int n = P.size(), k = 0;
+  vector<point> H(2*n);
+  
+  // Sort points lexicographically
+  sort(P.begin(), P.end());
+  
+  // Build lower hull
+  for (int i = 0; i < n; i++) {
+    while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--;
+    H[k++] = P[i];
+  }
+  
+  // Build upper hull
+  for (int i = n-2, t = k+1; i >= 0; i--) {
+    while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--;
+    H[k++] = P[i];
+  }
+  
+  H.resize(k);
+  return H;
+}
diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp
index 6984be9..5369b50 100644
--- a/geometry/formulars.cpp
+++ b/geometry/formulars.cpp
@@ -55,4 +55,29 @@ bool pointOnLine(pt a, pt b, pt p) {
 //testet, ob d in der gleichen Ebene liegt wie a, b, und c
 bool isCoplanar(pt a, pt b, pt c, pt d) {
 	return (b - a) * (c - a) * (d - a) == 0;
-}
\ No newline at end of file
+}
+//berechnet den Flaecheninhalt eines Polygons (nicht selbstschneidend)
+double areaOfPolygon(vector<pt> &polygon) { //jeder Eckpunkt nur einmal im Vektor
+	double res = 0; int n = polygon.size();
+	for (int i = 0; i < (int)polygon.size(); i++)
+		res += real(polygon[i]) * imag(polygon[(i + 1) % n]) - real(polygon[(i + 1) % n]) * imag(polygon[i]);
+	return 0.5 * abs(res);
+}
+//testet, ob sich zwei Rechtecke (p1, p2) und (p3, p4) schneiden (jeweils gegenueberliegende Ecken)
+bool rectIntersection(pt p1, pt p2, pt p3, pt p4) {
+	double minx12 = min(real(p1), real(p2)), maxx12 = max(real(p1), real(p2));
+	double minx34 = min(real(p3), real(p4)), maxx34 = max(real(p3), real(p4));
+	double miny12 = min(imag(p1), imag(p2)), maxy12 = max(imag(p1), imag(p2));
+	double miny34 = min(imag(p3), imag(p4)), maxy34 = max(imag(p3), imag(p4));
+	return (maxx12 >= minx34) && (maxx34 >= minx12) && (maxy12 >= miny34) && (maxy34 >= miny12);
+}
+//testet, ob ein Punkt im Polygon liegt (beliebige Polygone)
+bool pointInPolygon(pt p, vector<pt> &polygon) { //jeder Eckpunkt nur einmal im Vektor
+	pt rayEnd = p + pt(1, 1000000);
+	int counter = 0, n = polygon.size();
+	for (int i = 0; i < n; i++) {
+		pt start = polygon[i], end = polygon[(i + 1) % n];
+		if (lineSegmentIntersection(p, rayEnd, start, end)) counter++;
+	}
+	return counter & 1;
+}
diff --git a/geometry/geometry.tex b/geometry/geometry.tex
index b48a51e..de7b2f6 100644
--- a/geometry/geometry.tex
+++ b/geometry/geometry.tex
@@ -6,5 +6,8 @@
 \subsection{Geraden}
 \lstinputlisting{geometry/lines.cpp}
 
+\subsection{Konvexe Hülle}
+\lstinputlisting{geometry/convexHull.cpp}
+
 \subsection{Formeln - \lstinline{std::complex}}
-\lstinputlisting{geometry/formulars.cpp}
\ No newline at end of file
+\lstinputlisting{geometry/formulars.cpp}
diff --git a/graph/LCA.cpp b/graph/LCA.cpp
new file mode 100644
index 0000000..b4e6bdd
--- /dev/null
+++ b/graph/LCA.cpp
@@ -0,0 +1,16 @@
+//RMQ muss hinzugefuegt werden!
+vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
+vector<vector<int>> graph(MAX_N);
+
+void initLCA(int gi, int d, int &c) {
+	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
+	for(int gn : graph[gi]) {
+		initLCA(gn, d+1, c);
+		visited[c] = gi, depth[c] = d, c++;
+	}
+}
+//[a, b]
+int getLCA(int a, int b) {
+	return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))];
+}
+//=> int c = 0; initLCA(0,0,c); initRMQ(); done!
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
new file mode 100644
index 0000000..b99a286
--- /dev/null
+++ b/graph/articulationPoints.cpp
@@ -0,0 +1,47 @@
+vector< vector<int> > adjlist;
+vector<int> low;
+vector<int> d;
+vector<bool> isArtPoint;
+vector< vector<int> > bridges; //nur fuer Bruecken
+int counter = 0;
+
+void visit(int v, int parent) {
+	d[v] = low[v] = ++counter;
+	int numVisits = 0, maxlow = 0;
+	
+	for (vector<int>::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) {
+		if (d[*vit] == 0) {
+			numVisits++;
+			visit(*vit, v);
+			if (low[*vit] > maxlow) {
+				maxlow = low[*vit];
+			}
+			
+			if (low[*vit] > d[v]) { //nur fuer Bruecken
+				bridges[v].push_back(*vit); bridges[*vit].push_back(v);
+			}
+			
+			low[v] = min(low[v], low[*vit]);
+		} else {
+			if (d[*vit] < low[v]) {
+				low[v] = d[*vit];
+			}
+		}
+	}
+	
+	if (parent == -1) {
+		if (numVisits > 1) isArtPoint[v] = true;
+	} else {
+		if (maxlow >= d[v]) isArtPoint[v] = true;
+	}
+}
+
+void findArticulationPoints() {
+	low.clear(); low.resize(adjlist.size());
+	d.clear(); d.assign(adjlist.size(), 0);
+	isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false);
+	bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken
+	for (int v = 0; v < (int)adjlist.size(); v++) {
+		if (d[v] == 0) visit(v, -1);
+	}
+}
\ No newline at end of file
diff --git a/graph/euler.cpp b/graph/euler.cpp
new file mode 100644
index 0000000..74b3399
--- /dev/null
+++ b/graph/euler.cpp
@@ -0,0 +1,41 @@
+vector< vector<int> > adjlist;
+vector< vector<int> > otherIdx;
+vector<int> cycle;
+vector<int> validIdx;
+
+void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n.
+	int neighA = adjlist[n][a];
+	int neighB = adjlist[n][b];
+	int idxNeighA = otherIdx[n][a];
+	int idxNeighB = otherIdx[n][b];
+	swap(adjlist[n][a], adjlist[n][b]);
+	swap(otherIdx[n][a], otherIdx[n][b]);
+	otherIdx[neighA][idxNeighA] = b;
+	otherIdx[neighB][idxNeighB] = a;
+}
+
+void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante).
+	int other = adjlist[n][i];
+	if (other == n) { //Schlingen
+		validIdx[n]++;
+		return;
+	}
+	int otherIndex = otherIdx[n][i];
+	validIdx[n]++;
+	if (otherIndex != validIdx[other]) {
+		swapEdges(other, otherIndex, validIdx[other]);
+	}
+	validIdx[other]++;
+}
+
+//findet Eulerzyklus an Knoten n startend
+//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok)
+//teste vorher, ob Eulerzyklus ueberhaupt existiert!
+void euler(int n) {
+	while (validIdx[n] < (int)adjlist[n].size()) {
+		int nn = adjlist[n][validIdx[n]];
+		removeEdge(n, validIdx[n]);
+		euler(nn);
+	}
+	cycle.push_back(n); //Zyklus am Ende in cycle
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index 8d01e97..e3fd262 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,5 +1,8 @@
 \section{Graphen}
 
+\subsection{Lowest Common Ancestor}
+\lstinputlisting{graph/LCA.cpp}
+
 \subsection{Kürzeste Wege}
 
 \subsubsection{Algorithmus von \textsc{Dijkstra}}
@@ -17,5 +20,17 @@ Alle kürzesten Pfade im Graphen.
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
+\subsection{Artikulationspunkte und Brücken}
+\lstinputlisting{graph/articulationPoints.cpp}
+
+\subsection{Eulertouren}
+\begin{itemize}
+	\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+	\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+	\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
+	\item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher.
+\end{itemize}
+\lstinputlisting{graph/euler.cpp}
+
 \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
-\lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
+\lstinputlisting{graph/edmondsKarp.cpp}
diff --git a/math/factor.cpp b/math/factor.cpp
new file mode 100644
index 0000000..43aeae3
--- /dev/null
+++ b/math/factor.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef unsigned long long ll;
+
+const ll PRIME_SIZE = 10000000;
+vector<int> primes;
+
+//Call before calculating anything
+void primeSieve() {
+	vector<int> isPrime(PRIME_SIZE,true);
+	for(ll i = 2; i < PRIME_SIZE; i+=2) {
+		if(isPrime[i]) {
+			primes.push_back(i);
+			if(i*i <= PRIME_SIZE) {
+				for(ll j = i; i*j < PRIME_SIZE; j+=2) isPrime[i*j] = false;
+			}
+		}
+		if(i == 2)
+			i--;
+	}
+} 
+
+//Factorize the number n
+vector<int> factorize(ll n) {
+	vector<int> factor;
+	ll num = n;
+	int pos = 0;
+	while(num != 1)  {
+		if(num % primes[pos] == 0) {
+			num /= primes[pos];
+			factor.push_back(primes[pos]);
+		}
+		else
+			pos++;
+		if(primes[pos]*primes[pos] > n)
+			break;
+	}
+	if(num != 1)
+		factor.push_back(num);
+	return factor;
+	
+}
diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp
new file mode 100644
index 0000000..e42e4ab
--- /dev/null
+++ b/math/lgsFp.cpp
@@ -0,0 +1,27 @@
+void normalLine(ll n, ll line, ll p) { //normalisiert Zeile line
+	ll factor = multInv(mat[line][line], p); //Implementierung von oben
+	for (ll i = 0; i <= n; i++) {
+		mat[line][i] *= factor;
+		mat[line][i] %= p;
+	}
+}
+
+void takeAll(ll n, ll line, ll p) { //zieht Vielfaches von line von allen anderen Zeilen ab
+	for (ll i = 0; i < n; i++) {
+		if (i == line) continue;
+		ll diff = mat[i][line]; //abziehen
+		for (ll j = 0; j <= n; j++) {
+			mat[i][j] -= (diff * mat[line][j]) % p;
+			while (mat[i][j] < 0) {
+				mat[i][j] += p;
+			}
+		}
+	}
+}
+
+void gauss(ll n, ll p) { //n x n+1-Matrix, Koerper F_p
+	for (ll line = 0; line < n; line++) {
+		normalLine(n, line, p);
+		takeAll(n, line, p);
+	}
+}
\ No newline at end of file
diff --git a/math/math.tex b/math/math.tex
index f82ab65..973103a 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -15,6 +15,19 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 	\end{itemize}
 	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
 \end{description}
+\lstinputlisting{math/multInv.cpp}
+
+\subsubsection{Faktorisierung}
+\lstinputlisting{math/factor.cpp}
+
+\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
+\lstinputlisting{math/modExp.cpp}
+
+\subsection{LGS über $\mathbb{F}_p$}
+\lstinputlisting{math/lgsFp.cpp}
 
 \subsection{Binomialkoeffizienten}
-\lstinputlisting{math/binomial.cpp}
\ No newline at end of file
+\lstinputlisting{math/binomial.cpp}
+
+\subsection{Primzahlsieb von Eratosthenes}
+\lstinputlisting{math/primeSieve.cpp}
diff --git a/math/modExp.cpp b/math/modExp.cpp
new file mode 100644
index 0000000..f738268
--- /dev/null
+++ b/math/modExp.cpp
@@ -0,0 +1,7 @@
+ll modPow(ll b, ll e, ll p) {
+	if (e == 0) return 1;
+	if (e == 1) return b;
+	ll half = modPow(b, e / 2, p), res = (half * half) % p;
+	if (e & 1) res *= b; res %= p;
+	return res;
+}
\ No newline at end of file
diff --git a/math/multInv.cpp b/math/multInv.cpp
new file mode 100644
index 0000000..f9db815
--- /dev/null
+++ b/math/multInv.cpp
@@ -0,0 +1,5 @@
+ll multInv(ll n, ll p) { //berechnet das multiplikative Inverse von n in F_p
+	extendedEuclid(n, p); //implementierung von oben
+	x += ((x / p) + 1) * p;
+	return x % p;
+}
\ No newline at end of file
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
new file mode 100644
index 0000000..4c82bbe
--- /dev/null
+++ b/math/primeSieve.cpp
@@ -0,0 +1,22 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef unsigned long long ll;
+
+vector<int> primeSieve(ll n) {
+	vector<int> primes;
+	vector<int> isPrime(n,true);
+	for(ll i = 2; i < n; i+=2) {
+		if(isPrime[i]) {
+			primes.push_back(i);
+			if(i*i <= n) {
+				for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false;
+			}
+		}
+		if(i == 2)
+			i--;
+	}
+	return primes;
+} 
diff --git a/string/LCSubSequence.cpp b/string/LCSubSequence.cpp
new file mode 100644
index 0000000..0ea2913
--- /dev/null
+++ b/string/LCSubSequence.cpp
@@ -0,0 +1,17 @@
+string lcss(string &a, string &b) {
+	int m[a.length() + 1][b.length() + 1], x=0, y=0;
+	memset(m, 0, sizeof(m));
+	for(int y = a.length() - 1; y >= 0; y--) {
+		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];
+	string res;
+	while(x < b.length() && y < a.length()) {
+		if(a[y] == b[x]) res += a[y++], x++;
+		else if(m[y][x+1] > m[y+1][x+1]) x++;
+		else y++;
+	}
+	return res;
+}
diff --git a/string/LCSubstring.cpp b/string/LCSubstring.cpp
new file mode 100644
index 0000000..69d636f
--- /dev/null
+++ b/string/LCSubstring.cpp
@@ -0,0 +1,26 @@
+//longest common substring.
+struct lcse {
+	int i = 0, s = 0;
+};
+string lcp(string s[2]) {
+	if(s[0].length() == 0 || s[1].length() == 0) return "";
+	vector<lcse> a(s[0].length()+s[1].length());
+	for(int k = 0; k < a.size(); k++) a[k].i=(k < s[0].length() ? k : k - s[0].length()), a[k].s = (k < s[0].length() ? 0 : 1);
+	sort(a.begin(), a.end(), [&] (const lcse &u, const lcse &l) {
+		int ui = u.i, li = l.i;
+		while(ui < s[u.s].length() && li < s[l.s].length()) {
+			if(s[u.s][ui] < s[l.s][li]) return true;
+			else if(s[u.s][ui] > s[l.s][li]) return false;
+			ui++; li++;
+		}
+		return !(ui < s[u.s].length());
+	});
+	int r = 0, m=0, c=0;
+	for(int i = 0; i < a.size() - 1; i++) { 
+		if(a[i].s == a[i+1].s) continue;
+		c = 0;
+		while(a[i].i+c < s[a[i].s].length() && a[i+1].i+c < s[a[i+1].s].length() && s[a[i].s][a[i].i+c] == s[a[i+1].s][a[i+1].i+c]) c++;
+		if(c > m) r=i, m=c;
+	}
+	return m == 0 ? "" : s[a[r].s].substr(a[r].i, m);
+}
diff --git a/string/kmp.cpp b/string/kmp.cpp
new file mode 100644
index 0000000..f7c3630
--- /dev/null
+++ b/string/kmp.cpp
@@ -0,0 +1,35 @@
+#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);
+	b[0] = -1;
+	int i = 0, j = -1;
+	while(i < sub.size()) {
+		while(j >= 0 && sub[i] != sub[j])
+			j = b[j];
+		i++; j++;
+		b[i] = j;
+	}
+	return b;
+}
+
+//Searching after Substring sub in s
+vector<int> kmp_search(string& s, string& sub) {
+	vector<int> pre = kmp_preprocessing(sub);
+	vector<int> result;
+	int i = 0, j = -1;
+	while(i < s.size()) {
+		while(j >= 0 && s[i] != sub[j])
+			j = pre[j];
+		i++; j++;
+		if(j == sub.size()) {
+			result.push_back(i-j);
+			j = pre[j];
+		}
+	}
+	return result;
+}
diff --git a/string/string.tex b/string/string.tex
new file mode 100644
index 0000000..61385fc
--- /dev/null
+++ b/string/string.tex
@@ -0,0 +1,16 @@
+\section{Strings}
+
+\subsection{\textsc{Knuth-Morris-Pratt}-Algorithmus}
+\lstinputlisting{string/kmp.cpp}
+
+\subsection{Trie}
+\lstinputlisting{string/trie.cpp}
+
+\subsection{Suffix-Array}
+\lstinputlisting{string/suffixArray.cpp}
+
+\subsection{Longest Common Substring}
+\lstinputlisting{string/LCSubstring.cpp}
+
+\subsection{Longest Common Subsequence}
+\lstinputlisting{string/LCSubSequence.cpp}
diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp
new file mode 100644
index 0000000..73c7aff
--- /dev/null
+++ b/string/suffixArray.cpp
@@ -0,0 +1,36 @@
+//longest common substring in one string (overlapping not excluded)
+//contains suffix array:--------------------------------------------------------------------
+int cmp(string &s,vector<vector<int>> &v, int i, int vi, int u, int l) {
+	int vi2 = (vi + 1) % 2, u2 = u + i / 2, l2 = l + i / 2; 
+	if(i == 1) return s[u] - s[l];
+	else if (v[vi2][u] != v[vi2][l]) return (v[vi2][u] - v[vi2][l]);
+	else { //beide groesser tifft nicht mehr ein, da ansonsten vorher schon unterschied in Laenge
+		if(u2 >= s.length()) return -1;
+		else if(l2 >= s.length()) return 1;
+		else return v[vi2][u2] - v[vi2][l2];
+	}
+}
+
+string lcsub(string s) {
+	if(s.length() == 0) return "";
+	vector<int> a(s.length());
+	vector<vector<int>> v(2, vector<int>(s.length(), 0));
+	int vi = 0;
+	for(int k = 0; k < a.size(); k++) a[k] = k;	
+	for(int i = 1; i <= s.length(); i *= 2, vi = (vi + 1) % 2) {
+		sort(a.begin(), a.end(), [&] (const int &u, const int &l) {
+			return cmp(s, v, i, vi, u, l) < 0;
+		});
+		v[vi][a[0]] = 0;
+		for(int z = 1; z < a.size(); z++) v[vi][a[z]] = v[vi][a[z-1]] + (cmp(s, v, i, vi, a[z], a[z-1]) == 0 ? 0 : 1);
+	}
+//-------------------------------------------------------------------------------------------
+	int r = 0, m=0, c=0;
+	for(int i = 0; i < a.size() - 1; i++) {
+		c = 0;
+		while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++;
+		if(c > m) r=i, m=c;
+	}
+	return m == 0 ? "" : s.substr(a[r], m);
+}
+
diff --git a/string/trie.cpp b/string/trie.cpp
new file mode 100644
index 0000000..f4b979c
--- /dev/null
+++ b/string/trie.cpp
@@ -0,0 +1,25 @@
+//nur fuer kleinbuchstaben!
+struct node {
+	node *(e)[26];
+	int c = 0;//anzahl der woerter die an dem node enden.
+	node() { for(int i = 0; i < 26; i++) e[i] = NULL; }	
+};
+
+void insert(node *root, string *txt, int s) {
+	if(s >= txt->length()) root->c++;
+	else {
+		int idx = (int)((*txt).at(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) {
+	if(s >= txt->length()) return root->c;
+	int idx = (int)((*txt).at(s) - 'a');
+	if(root->e[idx] != NULL) {
+			return contains(root->e[idx], txt, s+1);
+	} else return 0;
+}
diff --git a/tcr.pdf b/tcr.pdf
index af23bcc..29cfc40 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/tcr.tex b/tcr.tex
index 4dce95e..cea7d08 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -8,6 +8,7 @@
 \usepackage{amssymb}
 
 \usepackage{enumitem}
+\setlist{nosep}
 
 \usepackage{color}
 \definecolor{darkred}{rgb}{0.72,0.07,0.07}
@@ -43,19 +44,25 @@
 
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry}
 
+\usepackage{multicol}
+
 \title{Team Contest Reference}
 \author{ChaosKITs \\ Karlsruhe Institute of Technology}
 
 \begin{document}
 
 \maketitle
-\tableofcontents
+\setlength{\columnsep}{1cm}
+\begin{multicols}{2}
+	\tableofcontents
+\end{multicols}
 \newpage
 
 \input{datastructures/datastructures}
 \input{graph/graph}
 \input{geometry/geometry}
 \input{math/math}
+\input{string/string}
 \input{sonstiges/sonstiges}
 
 \end{document}
\ No newline at end of file