From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- content/string/string.tex | 132 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 132 insertions(+) create mode 100644 content/string/string.tex (limited to 'content/string/string.tex') diff --git a/content/string/string.tex b/content/string/string.tex new file mode 100644 index 0000000..bedabfb --- /dev/null +++ b/content/string/string.tex @@ -0,0 +1,132 @@ +\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}{Rolling Hash} + \sourcecode{string/rollingHash.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} + +\begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome} + \begin{methods} + \method{init}{transformiert \code{string a}}{n} + \method{manacher}{berechnet Längen der Palindrome in longest}{n} + \end{methods} + \sourcecode{string/manacher.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} + +\columnbreak +\begin{algorithm}{\textsc{Aho-Corasick}-Automat} + \begin{methods}[ll] + sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}} + \end{methods} + \begin{enumerate} + \item mit \code{addString(pattern, idx)} Patterns hinzufügen. + \item rufe \code{buildGraph()} auf + \item mit \code{state = go(state, idx)} in nächsten Zustand wechseln. + \item erhöhe dabei \code{dp[state]++} + \item rufe \code{dfs()} auf. In dp[pattern state] stehen die Anzahl der Matches + \end{enumerate} + \sourcecode{string/ahoCorasick.cpp} +\end{algorithm} +\clearpage + +\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