From f78fa78909c2254ac9cfd7d835cd12c20dbc77e7 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sat, 15 Oct 2016 16:44:01 +0200
Subject: Added terminals and comments to suffix automaton code.

---
 string/string.tex | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

(limited to 'string/string.tex')

diff --git a/string/string.tex b/string/string.tex
index 854b05a..51ee9b1 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -14,6 +14,26 @@
 
 \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}
-- 
cgit v1.2.3

