Added terminals and comments to suffix automaton code.

2 files changed, 33 insertions, 3 deletions

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}
diff --git a/string/suffixAutomaton.cpp b/string/suffixAutomaton.cpp
index 4e8abcf..7f4885c 100644
--- a/string/suffixAutomaton.cpp
+++ b/string/suffixAutomaton.cpp
@@ -15,8 +15,8 @@ struct SuffixAutomaton {
 		for (auto c : s) extend(c);
 	}
 
-	void extend(char c) { // Werte von c müssen bei 0 beginnen.
-		c -= 'a';
+	void extend(char c) {
+		c -= 'a'; // Werte von c müssen bei 0 beginnen.
 		int current = size++;
 		states[current].length = states[last].length + 1;
 		int pos = last;
@@ -58,5 +58,15 @@ struct SuffixAutomaton {
 		}
 		return ii(bestpos - best + 1, best);
 	}
-};
 
+	// Berechnet die Terminale des Automaten.
+	vector<int> calculateTerminals() {
+		vector<int> terminals;
+		int pos = last;
+		while (pos != -1) {
+			terminals.push_back(pos);
+			pos = states[pos].link;
+		}
+		return terminals;
+	}
+};