added fft string matching

4 files changed, 17 insertions, 3 deletions

diff --git a/math/math.tex b/math/math.tex
index 6d3d3f2..fe288dc 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -254,7 +254,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \sourcecode{math/gauss.cpp}
 
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
-Multipliziert Polynome $A$ und $B$.
+	Multipliziert Polynome $A$ und $B$.
 	\begin{itemize}
 		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$
 		\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
diff --git a/other/other.tex b/other/other.tex
index db3fd55..1a56919 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -149,11 +149,12 @@
 
 	\item \textbf{Satz von \textsc{Pick}:}
 	Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand.
-	Es gilt:
+	Es gilt:\vspace*{-\baselineskip}
 	\[
 		A = I + \frac{R}{2} - 1
 	\]
 
+\columnbreak
 	\item \textbf{Lemma von \textsc{Burnside}:}
 	Sei $G$ eine endliche Gruppe, die auf der Menge $X$ operiert.
 	Für jedes $g \in G$ sei $X^g$ die Menge der Fixpunkte bei Operation durch $g$, also $X^g = \{x \in X \mid g \bullet x = x\}$.
diff --git a/string/string.tex b/string/string.tex
index f426c61..0daaef2 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -107,7 +107,7 @@
 	\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 \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}
@@ -116,3 +116,16 @@
 	\end{methods}
 	\sourcecode{string/deBruijn.cpp}
 \end{algorithm}
+
+\begin{algorithm}{Pattern Matching mit Wildcards}
+	Gegeben zwei strings $A$ und $B$,$B$ enthält $k$ \emph{wildcards} enthält. Sei:
+	\begin{align*}
+		a_i&=\cos(\alpha_i) + i\sin(\alpha_i) &\text{ mit } \alpha_i&=\frac{2\pi A[i]}{\Sigma}\\
+		b_i&=\cos(\beta_i) + i\sin(\beta_i) &\text{ mit } \beta_i&=\begin{cases*}
+			\frac{2\pi B[\abs{B}-i-1]}{\Sigma} & falls $B[\abs{B}-i-1]\in\Sigma$ \\
+			0 & sonst
+		\end{cases*}
+	\end{align*}
+	$B$ matcht $A$ an stelle $i$ wenn $(b\cdot a)[|B|-1+i]=|B|-k$.
+	Benutze FFT um $(b\cdot a)$ zu berechnen.
+\end{algorithm}
diff --git a/tcr.pdf b/tcr.pdf
index 2b91879..9db2864 100644
--- a/tcr.pdf
+++ b/tcr.pdf