1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
\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}{Trie}
\sourcecode{string/trie.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}
\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}
\begin{algorithm}{Rolling Hash}
\sourcecode{string/rollingHash.cpp}
\end{algorithm}
\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}
\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-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-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}
\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}
|
