Test (#4)

* update

* moved content in subdir

* rename file

* add test setup

* add test setup

* add github action

* automaticly test all cpp files

* timeout after 10s

* setulimit and dont zero memory

* test build pdf

* install latexmk

* update

* update

* ngerman

* fonts

* removed old code

* add first test

* added tests

* test in sorted order

* more tests

* simplified test

* more tests

* fix suffix tree

* fixes and improvements

* done ust lst directly

* fix swap

* add links to pdf

* fix constants

* add primorial

* add comment

* various improvements

* more tests

* added missing stuf

* more tests

* fix tests

* more tests

* more tests

* more tests

* fix recursion?

* test trie

* more tests

* only use python temporarily for listings

* only use python temporarily for listings

* more tests

* fix longestCommonSubstring

* more tests

* more tests

* made code more similiar

* fix?

* more tests

* more tests

* more tests

* add ahoCorasick test + limit 4GB stack size

* more tests

* fix test

* add additional test

* more tests

* more tests

* fix?

* better fix

* fix virtual tree

* more tests

* more tests

* recursive closest pair

* more tests

* decrease limit

* new tests

* more tests

* fix name

* more tests

* add test

* new test

* more tests

* more tests

* more tests

* more tests

* new test and content

* new code

* new code

* larger tests

* fix and test

* new test

* new test

* update pdf

* remove comments

* new test

* more tests

* more testcases

* more tests

* increased limit

* more tests

* more tests

* more tests

* new tests

* more tests

* shortened code

* new test

* add basic tests for bigint

* more tests

* removed old files

* new test

* ignore some files

* more auto more ccw

* fix test

* more tests

* fix

* new tests

* more tests

* more tests

* stronger test

* actually verify delaunay...

* more tests

* fix header

* more tests

* run tests parallel?

* test parralel?

* add --missing

* separate workflows

* test

* is the pdf checked?

* separate workflows

* fix workflow

* more workflows

---------

Co-authored-by: Yidi <noob999noob999@gmail.com>

16 files changed, 0 insertions, 541 deletions

diff --git a/string/ahoCorasick.cpp b/string/ahoCorasick.cpp
deleted file mode 100644
index eac312c..0000000
--- a/string/ahoCorasick.cpp
+++ /dev/null
@@ -1,52 +0,0 @@
-constexpr ll ALPHABET_SIZE = 26, OFFSET = 'a';
-struct AhoCorasick {
-	struct vert {
-		int suffix = 0, ch, cnt = 0;
-		array<int, ALPHABET_SIZE> nxt = {};
-
-		vert(int p, int c) : suffix(-p), ch(c) {}
-	};
-	vector<vert> aho = {{0, -1}};
-
-	int addString(string &s) {
-		int v = 0;
-		for (auto c : s) {
-			int idx = c - OFFSET;
-			if (!aho[v].nxt[idx]) {
-				aho[v].nxt[idx] = sz(aho);
-				aho.emplace_back(v, idx);
-			}
-			v = aho[v].nxt[idx];
-		}
-		aho[v].cnt++;
-		return v; // trie node index of pattern (pattern state)
-	}
-
-	int getSuffix(int v) {
-		if (aho[v].suffix < 0) {
-			aho[v].suffix = go(getSuffix(-aho[v].suffix), aho[v].ch);
-		}
-		return aho[v].suffix;
-	}
-
-	int go(int v, int idx) { // Root is v=0, idx is char - OFFSET
-		if (aho[v].nxt[idx]) return aho[v].nxt[idx];
-		else return v == 0 ? 0 : go(getSuffix(v), idx);
-	}
-
-	vector<vector<int>> adj;
-	vector<ll> dp;
-	void buildGraph() {
-		adj.resize(sz(aho));
-		dp.assign(sz(aho), 0);
-		for (int i = 1; i < sz(aho); i++) {
-			adj[getSuffix(i)].push_back(i);
-	}}
-
-	void dfs(int v = 0) { // dp on tree
-		for (int u : adj[v]) {
-			//dp[u] = dp[v] + aho[u].cnt; // pattern count
-			dfs(u);
-			dp[v] += dp[u]; // no of matches
-	}}
-};
diff --git a/string/deBruijn.cpp b/string/deBruijn.cpp
deleted file mode 100644
index e829137..0000000
--- a/string/deBruijn.cpp
+++ /dev/null
@@ -1,7 +0,0 @@
-string deBruijn(int n, char mi = '0', char ma = '1') {
-	string res, c(1, mi);
-	do {
-		if (n % sz(c) == 0) res += c;
-	} while(next(c, n, mi, ma));
-	return res;
-}
diff --git a/string/duval.cpp b/string/duval.cpp
deleted file mode 100644
index bf36cce..0000000
--- a/string/duval.cpp
+++ /dev/null
@@ -1,21 +0,0 @@
-vector<pair<int, int>> duval(const string& s) {
-	vector<pair<int, int>> res;
-	for (int i = 0; i < sz(s);) {
-		int j = i + 1, k = i;
-		for (; j < sz(s) && s[k] <= s[j]; j++) {
-			if (s[k] < s[j]) k = i;
-			else k++;
-		}
-		while (i <= k) {
-			res.push_back({i, i + j - k});
-			i += j - k;
-	}}
-	return res;
-}
-
-int minrotation(const string& s) {
-	auto parts = duval(s+s);
-	for (auto [l, r] : parts) {
-		if (l < sz(s) && r >= sz(s)) {
-			return l;
-}}}
diff --git a/string/kmp.cpp b/string/kmp.cpp
deleted file mode 100644
index 421479e..0000000
--- a/string/kmp.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-vector<int> kmpPreprocessing(const string& sub) {
-	vector<int> b(sz(sub) + 1);
-	b[0] = -1;
-	for (int i = 0, j = -1; i < sz(sub);) {
-		while (j >= 0 && sub[i] != sub[j]) j = b[j];
-		b[++i] = ++j;
-	}
-	return b;
-}
-vector<int> kmpSearch(const string& s, const string& sub) {
-	vector<int> result, pre = kmpPreprocessing(sub);
-	for (int i = 0, j = 0; i < sz(s);) {
-		while (j >= 0 && s[i] != sub[j]) j = pre[j];
-		i++; j++;
-		if (j == sz(sub)) {
-			result.push_back(i - j);
-			j = pre[j];
-	}}
-	return result;
-}
diff --git a/string/longestCommonSubsequence.cpp b/string/longestCommonSubsequence.cpp
deleted file mode 100644
index 109fe72..0000000
--- a/string/longestCommonSubsequence.cpp
+++ /dev/null
@@ -1,15 +0,0 @@
-string lcss(const string& a, const string& b) {
-	vector<vector<int>> m(sz(a) + 1, vector<int>(sz(b) + 1));
-	for (int i = sz(a) - 1; i >= 0; i--) {
-		for (int j = sz(b) - 1; j >= 0; j--) {
-			if (a[i] == b[j]) m[i][j] = 1 + m[i+1][j+1];
-			else m[i][j] = maj(m[i+1][j], m[i][j+1]);
-	}} // Für die Länge: return m[0][0];
-	string res;
-	for (int j = 0, i = 0; j < sz(b) && i < sz(a);) {
-		if (a[i] == b[j]) res += a[i++], j++;
-		else if (m[i][j+1] > m[i+1][j]) j++;
-		else i++;
-	}
-	return res;
-}
diff --git a/string/lyndon.cpp b/string/lyndon.cpp
deleted file mode 100644
index 858c3db..0000000
--- a/string/lyndon.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-bool next(string& s, int n, char mi = '0', char ma = '1') {
-	for (int i = sz(s), j = sz(s); i < n; i++)
-		s.push_back(s[i % j]);
-	while(!s.empty() && s.back() == ma) s.pop_back();
-	if (s.empty()) {
-		s = mi;
-		return false;
-	} else {
-		s.back()++;
-		return true;
-}}
diff --git a/string/manacher.cpp b/string/manacher.cpp
deleted file mode 100644
index 112bd55..0000000
--- a/string/manacher.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-vector<int> manacher(const string& t) {
-	//transforms "aa" to ".a.a." to find even length palindromes
-	string s(sz(t) * 2 + 1, '.');
-	for (int i = 0; i < sz(t); i++) s[2 * i + 1] = t[i];
-
-	int mid = 0, r = 0, n = sz(s);
-	vector<int> pal(n);
-	for (int i = 1; i < n - 1; i++) {
-		if (r > i) pal[i] = min(r - i, pal[2 * mid - i]);
-		while (pal[i] < min(i, n - i - 1) &&
-		       s[i + pal[i] + 1] == s[i - pal[i] - 1]) {
-			pal[i]++;
-		}
-		if (i + pal[i] > r) mid = i, r = i + pal[i];
-	}
-
-	//convert lengths to constructed string s (optional)
-	//for (int i = 0; i < n; i++) pal[i] = 2 * pal[i] + 1;
-	return pal;
-}
diff --git a/string/rollingHash.cpp b/string/rollingHash.cpp
deleted file mode 100644
index 00e2273..0000000
--- a/string/rollingHash.cpp
+++ /dev/null
@@ -1,16 +0,0 @@
-// q = 29, 53, 101, 257, 1009, 65'537
-// or choose q random from [sigma, m)
-// m = 1'500'000'001, 1'600'000'009, 1'700'000'009
-template<ll M, ll Q>
-struct Hasher {
-	vector<ll> power = {1}, pref = {0};
-	Hasher(const string& s) {
-		for (auto x : s) {
-			power.push_back(power.back() * Q % M);
-			pref.push_back((pref.back() * Q % M + x) % M);
-	}}
-
-	ll hash(int l, int r) {	// Berechnet hash(s[l..r)).
-		return (pref[r] - power[r-l] * pref[l] % M + M) % M;
-	}
-};
diff --git a/string/rollingHash2.cpp b/string/rollingHash2.cpp
deleted file mode 100644
index f60db2e..0000000
--- a/string/rollingHash2.cpp
+++ /dev/null
@@ -1,18 +0,0 @@
-// M = 1.7e9 + 9, 1e18L + 9, 2.2e18L + 7
-struct Hash {
-	static constexpr ll M = 3e18L + 37;
-	static constexpr ll Q = 318LL << 53; // Random in [SIGMA+1, M)
-	vector<ll> pref = {0}, power = {1};
-
-	Hash(const string& s) {
-		for (auto c : s) {
-			pref.push_back((mul(pref.back(), Q) + c + M) % M);
-			power.push_back(mul(power.back(), Q));
-	}}
-
-	ll operator()(int l, int r) {
-		return (pref[r] - mul(power[r-l], pref[l]) + M) % M;
-	}
-
-	static ll mul(__int128 a, ll b) {return a * b % M;}
-};
diff --git a/string/rollingHashCf.cpp b/string/rollingHashCf.cpp
deleted file mode 100644
index b055b29..0000000
--- a/string/rollingHashCf.cpp
+++ /dev/null
@@ -1,17 +0,0 @@
-// q = 29, 53, 101, 257, 1009, 65'537
-// or choose q random from [sigma, m)
-// m = 1'500'000'001, 1'600'000'009, 1'700'000'009
-struct Hasher {
-	vector<ll> power = {1}, pref = {0};
-	ll m, q; char c;
-	Hasher(const string& s, ll m, ll q, char c) :
-	       m(m), q(q), c(c) {
-		for (char x : s) {
-			power.push_back(power.back() * q % m);
-			pref.push_back((pref.back() * q % m + (x - c)) % m);
-	}}
-
-	ll hash(int l, int r) {	 // Berechnet hash(s[l..r)).
-		return (pref[r] - power[r-l] * pref[l] % m + m) % m;
-	}
-};
diff --git a/string/string.tex b/string/string.tex
deleted file mode 100644
index dbea36c..0000000
--- a/string/string.tex
+++ /dev/null
@@ -1,132 +0,0 @@
-\section{Strings}
-
-\begin{algorithm}{\textsc{Knuth-Morris-Pratt}-Algorithmus}
-	\begin{methods}
-		\method{kmpSearch}{sucht \code{sub} in \code{s}}{\abs{s}+\abs{sub}}
-	\end{methods}
-	\sourcecode{string/kmp.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Z-Algorithmus}
-	\begin{methods}[ll]
-		$z_i\coloneqq$ Längstes gemeinsames Präfix von $s_0\cdots s_{n-1}$ und $s_i\cdots s_{n-1}$ & \runtime{n}
-	\end{methods}
-	Suchen: Z-Algorithmus auf \code{P\$S} ausführen, Positionen mit $z_i=\abs{P}$ zurückgeben
-	\sourcecode{string/z.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Rolling Hash}
-	\sourcecode{string/rollingHash2.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Pattern Matching mit Wildcards}
-	Gegeben zwei strings $A$ und $B$,$B$ enthält $k$ \emph{wildcards} enthält. Sei:
-	\begin{align*}
-		a_i&=\cos(\alpha_i) + i\sin(\alpha_i) &\text{ mit } \alpha_i&=\frac{2\pi A[i]}{\Sigma}\\
-		b_i&=\cos(\beta_i) + i\sin(\beta_i) &\text{ mit } \beta_i&=\begin{cases*}
-			\frac{2\pi B[\abs{B}-i-1]}{\Sigma} & falls $B[\abs{B}-i-1]\in\Sigma$ \\
-			0 & sonst
-		\end{cases*}
-	\end{align*}
-	$B$ matcht $A$ an stelle $i$ wenn $(b\cdot a)[|B|-1+i]=|B|-k$.
-	Benutze FFT um $(b\cdot a)$ zu berechnen.
-\end{algorithm}
-
-\begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome}
-	\begin{methods}
-		\method{init}{transformiert \code{string a}}{n}
-		\method{manacher}{berechnet Längen der Palindrome in longest}{n}
-	\end{methods}
-	\sourcecode{string/manacher.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Longest Common Subsequence}
-	\begin{methods}
-		\method{lcss}{findet längste gemeinsame Sequenz}{\abs{a}\*\abs{b}}
-	\end{methods}
-	\sourcecode{string/longestCommonSubsequence.cpp}
-\end{algorithm}
-
-\columnbreak
-\begin{algorithm}{\textsc{Aho-Corasick}-Automat}
-	\begin{methods}[ll]
-		sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}}
-	\end{methods}
-	\begin{enumerate}
-		\item mit \code{addString(pattern, idx)} Patterns hinzufügen.
-        \item rufe \code{buildGraph()} auf
-		\item mit \code{state = go(state, idx)} in nächsten Zustand wechseln.
-        \item erhöhe dabei \code{dp[state]++}
-        \item rufe \code{dfs()} auf. In dp[pattern state] stehen die Anzahl der Matches
-	\end{enumerate}
-	\sourcecode{string/ahoCorasick.cpp}
-\end{algorithm}
-\clearpage
-
-\begin{algorithm}{Lyndon und De-Bruijn}
-	\begin{itemize}
-		\item \textbf{Lyndon-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen.
-		\item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von Lyndon-Worten zerlegt werden.
-		\item Für Lyndon-Worte $u, v$ mit $u<v$ gilt, dass $uv$ auch ein Lyndon-Wort ist.
-	\end{itemize}
-	\begin{methods}
-		\method[, Durchschnitt $\Theta(1)$]{next}{lexikographisch nächstes Lyndon-Wort}{n}
-		\method{duval}{zerlegt $s$ in Lyndon-Worte}{n}
-		\method{minrotation}{berechnet kleinste Rotation von $s$}{n}
-	\end{methods}
-	\sourcecode{string/lyndon.cpp}
-	\sourcecode{string/duval.cpp}
-	\begin{itemize}
-		\item \textbf{De-Bruijn-Sequenze $\boldsymbol{B(\Sigma, n)}$:}~~~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird.
-		\item es gibt $\frac{(k!)^{k^{n-1}}}{k^{n}}$ verschiedene $B(\Sigma, n)$
-		\item $B(\Sigma, n)$ hat Länge $\abs{\Sigma}^n$
-	\end{itemize}
-	\begin{methods}
-		\method{deBruijn}{berechnet ein festes $B(\Sigma, n)$}{\abs{\Sigma}^n}
-	\end{methods}
-	\sourcecode{string/deBruijn.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Suffix-Array}
-\begin{methods}
-	\method{SuffixArray}{berechnet ein Suffix Array}{\abs{s}\*\log^2(\abs{s})}
-	\method{lcp}{berechnet Länge des longest common prefix}{\log(\abs{s})}
-	\method{}{von \code{s[x]} und \code{s[y]}}{}
-\end{methods}
-\sourcecode{string/suffixArray.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Suffix-Baum}
-	\begin{methods}
-		\method{SuffixTree}{berechnet einen Suffixbaum}{\abs{s}}
-		\method{extend}{fügt den nächsten Buchstaben aus \code{s} ein}{1}
-	\end{methods}
-	\sourcecode{string/suffixTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Suffix-Automaton}
-	\sourcecode{string/suffixAutomaton.cpp}
-	\begin{itemize}
-		\item \textbf{Ist \textit{w} Substring von \textit{s}?}
-		Baue Automaten für \textit{s} und wende ihn auf \textit{w} an.
-		Wenn alle Übergänge vorhanden sind, ist \textit{w} Substring von \textit{s}.
-	
-		\item \textbf{Ist \textit{w} Suffix von \textit{s}?}
-		Wie oben und prüfe, ob Endzustand ein Terminal ist.
-	
-		\item \textbf{Anzahl verschiedener Substrings.}
-		Jeder Pfad im Automaten entspricht einem Substring.
-		Für einen Knoten ist die Anzahl der ausgehenden Pfade gleich der Summe über die Anzahlen der Kindknoten plus 1.
-		Der letzte Summand ist der Pfad, der in diesem Knoten endet.
-	
-		\item \textbf{Wie oft taucht \textit{w} in \textit{s} auf?}
-		Sei \textit{p} der Zustand nach Abarbeitung von \textit{w}.
-		Lösung ist Anzahl der Pfade, die in \textit{p} starten und in einem Terminal enden.
-		Diese Zahl lässt sich wie oben rekursiv berechnen.
-		Bei jedem Knoten darf nur dann plus 1 gerechnet werden, wenn es ein Terminal ist.
-	\end{itemize}
-\end{algorithm}
-
-\begin{algorithm}{Trie}
-	\sourcecode{string/trie.cpp}
-\end{algorithm}
diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp
deleted file mode 100644
index 8b698d2..0000000
--- a/string/suffixArray.cpp
+++ /dev/null
@@ -1,38 +0,0 @@
-constexpr int MAX_CHAR = 256;
-struct SuffixArray {
-	int n;
-	vector<int> SA, LCP;
-	vector<vector<int>> P;
-
-	SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n),
-		P(__lg(2 * n - 1) + 1, vector<int>(n)) {
-		P[0].assign(all(s));
-		iota(all(SA), 0);
-		sort(all(SA), [&](int a, int b) {return s[a] < s[b];});
-		vector<int> x(n);
-		for (int k = 1, c = 1; c < n; k++, c *= 2) {
-			iota(all(x), n - c);
-			for (int ptr = c; int i : SA) if (i >= c) x[ptr++] = i - c;
-
-			vector<int> cnt(k == 1 ? MAX_CHAR : n);
-			for (int i : P[k-1]) cnt[i]++;
-			partial_sum(all(cnt), begin(cnt));
-			for (int i : x | views::reverse) SA[--cnt[P[k-1][i]]] = i;
-
-			auto p = [&](int i) {return i < n ? P[k-1][i] : -1;};
-			for (int i = 1; i < n; i++) {
-				int a = SA[i-1], b = SA[i];
-				P[k][b] = P[k][a] + (p(a) != p(b) || p(a+c) != p(b+c));
-		}}
-		for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i-1], SA[i]);
-	}
-
-	int lcp(int x, int y) {//x & y are text-indices, not SA-indices
-		if (x == y) return n - x;
-		int res = 0;
-		for (int i = sz(P) - 1; i >= 0 && max(x, y) + res < n; i--) {
-			if (P[i][x + res] == P[i][y + res]) res |= 1 << i;
-		}
-		return res;
-	}
-};
diff --git a/string/suffixAutomaton.cpp b/string/suffixAutomaton.cpp
deleted file mode 100644
index 291f760..0000000
--- a/string/suffixAutomaton.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-constexpr int ALPHABET_SIZE = 26;
-constexpr char OFFSET = 'a';
-struct SuffixAutomaton {
-	struct State {
-		int len, link = -1;
-		array<int, ALPHABET_SIZE> next = {}; // map if large Alphabet
-		State(int l) : len(l) {}
-	};
-
-	vector<State> st = {State(0)};
-	int cur = 0;
-
-	SuffixAutomaton(const string& s) {
-		st.reserve(2 * sz(s));
-		for (auto c : s) extend(c - OFFSET);
-	}
-
-	void extend(int c) {
-		int p = cur;
-		cur = sz(st);
-		st.emplace_back(st[p].len + 1);
-		for (; p != -1 && !st[p].next[c]; p = st[p].link) {
-			st[p].next[c] = cur;
-		}
-		if (p == -1) st[cur].link = 0;
-		else {
-			int q = st[p].next[c];
-			if (st[p].len + 1 == st[q].len) {
-				st[cur].link = q;
-			} else {
-				st.emplace_back(st[p].len + 1);
-				st.back().link = st[q].link;
-				st.back().next = st[q].next;
-				for (; p != -1 && st[p].next[c] == q; p = st[p].link) {
-					st[p].next[c] = sz(st) - 1;
-				}
-				st[q].link = st[cur].link = sz(st) - 1;
-	}}}
-
-	vector<int> calculateTerminals() {
-		vector<int> terminals;
-		for (int p = cur; p != -1; p = st[p].link) {
-			terminals.push_back(p);
-		}
-		return terminals;
-	}
-
-	// Pair with start index (in t) and length of LCS.
-	pair<int, int> longestCommonSubstring(const string& t) {
-		int v = 0, l = 0, best = 0, bestp = 0;
-		for (int i = 0; i < sz(t); i++) {
-			int c = t[i] - OFFSET;
-			for (; v && !st[v].next[c]; v = st[v].link) l = st[v].len;
-			if (st[v].next[c]) v = st[v].next[c], l++;
-			if (l > best) best = l, bestp = i;
-		}
-		return {bestp - best + 1, best};
-	}
-};
diff --git a/string/suffixTree.cpp b/string/suffixTree.cpp
deleted file mode 100644
index caeeecf..0000000
--- a/string/suffixTree.cpp
+++ /dev/null
@@ -1,72 +0,0 @@
-struct SuffixTree {
-	struct Vert {
-		int start, end, suf;
-		map<char, int> next;
-	};
-	string s;
-	int needsSuffix, pos, remainder, curVert, curEdge, curLen;
-	// Each Vertex gives its children range as [start, end)
-	vector<Vert> tree = {Vert{-1, -1, 0 {}}};
-
-	SuffixTree(const string& s) : s(s) {
-		needsSuffix = remainder = curVert = curEdge = curLen = 0;
-		pos = -1;
-		for (int i = 0; i < sz(s); i++) extend();
-	}
-
-	int newVert(int start, int end) {
-		tree.push_back({start, end, 0, {}});
-		return sz(tree) - 1;
-	}
-
-	void addSuffixLink(int vert) {
-		if (needsSuffix) tree[needsSuffix].suf = vert;
-		needsSuffix = vert;
-	}
-
-	bool fullImplicitEdge(int vert) {
-		len = min(tree[vert].end, pos + 1) - tree[vert].start;
-		if (curLen >= len) {
-			curEdge += len;
-			curLen -= len;
-			curVert = vert;
-			return true;
-		} else {
-			return false;
-	}}
-
-	void extend() {
-		pos++;
-		needsSuffix = 0;
-		remainder++;
-		while (remainder) {
-			if (curLen == 0) curEdge = pos;
-			if (!tree[curVert].next.count(s[curEdge])) {
-				int leaf = newVert(pos, sz(s));
-				tree[curVert].next[s[curEdge]] = leaf;
-				addSuffixLink(curVert);
-			} else {
-				int nxt = tree[curVert].next[s[curEdge]];
-				if (fullImplicitEdge(nxt)) continue;
-				if (s[tree[nxt].start + curLen] == s[pos]) {
-					curLen++;
-					addSuffixLink(curVert);
-					break;
-				}
-				int split = newVert(tree[nxt].start,
-				                    tree[nxt].start + curLen);
-				tree[curVert].next[s[curEdge]] = split;
-				int leaf = newVert(pos, sz(s));
-				tree[split].next[s[pos]] = leaf;
-				tree[nxt].start += curLen;
-				tree[split].next[s[tree[nxt].start]] = nxt;
-				addSuffixLink(split);
-			}
-			remainder--;
-			if (curVert == 0 && curLen) {
-				curLen--;
-				curEdge = pos - remainder + 1;
-			} else {
-				curVert = tree[curVert].suf ? tree[curVert].suf : 0;
-	}}}
-};
\ No newline at end of file
diff --git a/string/trie.cpp b/string/trie.cpp
deleted file mode 100644
index 0544a9f..0000000
--- a/string/trie.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-// Zahlenwerte müssen bei 0 beginnen und zusammenhängend sein.
-constexpr int ALPHABET_SIZE = 2;
-struct node {
-	int words, wordEnds; vector<int> children;
-	node() : words(0), wordEnds(0), children(ALPHABET_SIZE, -1){}
-};
-vector<node> trie = {node()};
-
-int insert(vector<int>& word) {
-	int id = 0;
-	for (int c : word) {
-		trie[id].words++;
-		if (trie[id].children[c] < 0) {
-			trie[id].children[c] = sz(trie);
-			trie.emplace_back();
-		}
-		id = trie[id].children[c];
-	}
-	trie[id].words++;
-	trie[id].wordEnds++;
-	return id;
-}
-
-void erase(vector<int>& word) {
-	int id = 0;
-	for (int c : word) {
-		trie[id].words--;
-		id = trie[id].children[c];
-		if (id < 0) return;
-	}
-	trie[id].words--;
-	trie[id].wordEnds--;
-}
diff --git a/string/z.cpp b/string/z.cpp
deleted file mode 100644
index 069fa38..0000000
--- a/string/z.cpp
+++ /dev/null
@@ -1,10 +0,0 @@
-vector<int> Z(const string& s) {
-	int n = sz(s);
-	vector<int> z(n);
-	for (int i = 1, x = 0; i < n; i++) {
-		z[i] = max(0, min(z[i - x], x + z[x] - i));
-		while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
-			x = i, z[i]++;
-	}}
-	return z;
-}