diff options
Diffstat (limited to 'string/string.tex')
| -rw-r--r-- | string/string.tex | 142 |
1 files changed, 106 insertions, 36 deletions
diff --git a/string/string.tex b/string/string.tex index e13b516..f426c61 100644 --- a/string/string.tex +++ b/string/string.tex @@ -1,48 +1,118 @@ \section{Strings} -\subsection{\textsc{Knuth-Morris-Pratt}-Algorithmus} -\lstinputlisting{string/kmp.cpp} +\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} -\subsection{\textsc{Aho-Corasick}-Automat} -\lstinputlisting{string/ahoCorasick.cpp} +\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} -\subsection{Trie} -\lstinputlisting{string/trie.cpp} +\begin{algorithm}{Trie} + \sourcecode{string/trie.cpp} +\end{algorithm} -\subsection{Suffix-Baum} -\lstinputlisting{string/suffixTree.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} -\subsection{Suffix-Array} -\lstinputlisting{string/suffixArray.cpp} +\begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome} + \begin{methods} + \method{init}{transformiert \code{string a}}{n} + \method{manacher}{berechnet Länge der Palindrome}{n} + \end{methods} + \sourcecode{string/manacher.cpp} +\end{algorithm} -\subsection{Suffix-Automaton} -\lstinputlisting{string/suffixAutomaton.cpp} -\begin{itemize}[nosep] - \item \textbf{Ist \lstinline{w} Substring von \lstinline{s}?} - Baue Automaten für \lstinline{s} und wende ihn auf \lstinline{w} an. - Wenn alle Übergänge vorhanden sind, ist \lstinline{w} Substring von \lstinline{s}. +\begin{algorithm}{Rolling Hash} + \sourcecode{string/rollingHash.cpp} +\end{algorithm} - \item \textbf{Ist \lstinline{w} Suffix von \lstinline{s}?} - Wie oben. - Überprüfe am Ende, ob aktueller Zustand ein Terminal ist. +\begin{algorithm}{\textsc{Aho-Corasick}-Automat} + \begin{methods}[ll] + sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}+\abs{matches}} + \end{methods} + \begin{enumerate} + \item mit \code{addString(pattern, idx);} Patterns hinzufügen. + \item mit \code{state = go(state, idx)} in nächsten Zustand wechseln. + \item mit \code{state = getExit(state)} den exit Kanten folgen bis \code{state == 0} + \item dabei mit \code{aho[state].patterns} die Matches zählen + \end{enumerate} + \sourcecode{string/ahoCorasick.cpp} +\end{algorithm} - \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. +\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} - \item \textbf{Wie oft taucht \lstinline{w} in \lstinline{s} auf?} - Sei \lstinline{p} der Zustand nach Abarbeitung von \lstinline{w}. - Lösung ist Anzahl der Pfade, die in \lstinline{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} +\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} -\subsection{Longest Common Subsequence} -\lstinputlisting{string/longestCommonSubsequence.cpp} +\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. + Überprüfe am Ende, ob aktueller Zustand 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} -\subsection{Rolling Hash} -\lstinputlisting{string/rollingHash.cpp} - -\subsection{\textsc{Manacher}'s Algorithm, Longest Palindrome} -\lstinputlisting{string/manacher.cpp} +\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} |