blob: 56583302f6b9279faebc635d0f0d34403bf685a5 (
plain)
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
|
\section{Strings}
\subsection{\textsc{Knuth-Morris-Pratt}-Algorithmus}
\lstinputlisting{string/kmp.cpp}
\subsection{\textsc{Aho-Corasick}-Automat}
\lstinputlisting{string/ahoCorasick.cpp}
\subsection{Trie}
\lstinputlisting{string/trie.cpp}
\subsection{Suffix-Baum}
\lstinputlisting{string/suffixTree.cpp}
\subsection{Suffix-Array}
\lstinputlisting{string/suffixArray.cpp}
\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}.
\item \textbf{Ist \lstinline{w} Suffix von \lstinline{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 \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}
\subsection{Longest Common Subsequence}
\lstinputlisting{string/longestCommonSubsequence.cpp}
\subsection{Rolling Hash}
\lstinputlisting{string/rollingHash.cpp}
|
