From eb4bc75111da45a17604fdff2f9eed0977f93dff Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 14 Feb 2023 16:41:24 +0100
Subject: moved more stuff

---
 string/string.tex | 109 +++++++++++++++++++++++++++---------------------------
 1 file changed, 54 insertions(+), 55 deletions(-)

(limited to 'string/string.tex')

diff --git a/string/string.tex b/string/string.tex
index 0daaef2..6b83e2c 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -15,15 +15,21 @@
 	\sourcecode{string/z.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Trie}
-	\sourcecode{string/trie.cpp}
+\begin{algorithm}{Rolling Hash}
+	\sourcecode{string/rollingHash.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}
+\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}
@@ -34,8 +40,11 @@
 	\sourcecode{string/manacher.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Rolling Hash}
-	\sourcecode{string/rollingHash.cpp}
+\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}
 
 \begin{algorithm}{\textsc{Aho-Corasick}-Automat}
@@ -51,22 +60,46 @@
 	\sourcecode{string/ahoCorasick.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Suffix-Baum}
+\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{SuffixTree}{berechnet einen Suffixbaum}{\abs{s}}
-		\method{extend}{fügt den nächsten Buchstaben aus \code{s} ein}{1}
+		\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/suffixTree.cpp}
+	\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 den logest common prefix}{\log(\abs{s})}
+	\method{}{von \code{s[x]} und \code{s[y]}}{}
+\end{methods}
+\textbf{ACHTUNG:} \code{s} muss mit einem sentinel enden! \code{'\$'} oder \code{'#'}
+\sourcecode{string/suffixArray.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Suffix-Baum}
 	\begin{methods}
-		\method{SuffixArray}{berechnet ein Suffix Array}{\abs{s}\*\log^2(\abs{s})}
-		\method{lcp}{berechnet den logest common prefix}{\log(\abs{s})}
-		\method{}{von \code{s[x]} und \code{s[y]}}{}
+		\method{SuffixTree}{berechnet einen Suffixbaum}{\abs{s}}
+		\method{extend}{fügt den nächsten Buchstaben aus \code{s} ein}{1}
 	\end{methods}
-	\textbf{ACHTUNG:} \code{s} muss mit einem sentinel enden! \code{'\$'} oder \code{'#'}
-	\sourcecode{string/suffixArray.cpp}
+	\sourcecode{string/suffixTree.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Suffix-Automaton}
@@ -77,8 +110,7 @@
 		Wenn alle Übergänge vorhanden sind, ist \textit{w} Substring von \textit{s}.
 	
 		\item \textbf{Ist \textit{w} Suffix von \textit{s}?}
-		Wie oben.
-		Überprüfe am Ende, ob aktueller Zustand ein Terminal ist.
+		Wie oben und prüfe, ob Endzustand ein Terminal ist.
 	
 		\item \textbf{Anzahl verschiedener Substrings.}
 		Jeder Pfad im Automaten entspricht einem Substring.
@@ -93,39 +125,6 @@
 	\end{itemize}
 \end{algorithm}
 
-\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}{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.
+\begin{algorithm}{Trie}
+	\sourcecode{string/trie.cpp}
 \end{algorithm}
-- 
cgit v1.2.3