From 9906aa7bbf98bee5cdb91e80f6a2311e43129c7d Mon Sep 17 00:00:00 2001 From: Yidi Date: Wed, 20 Mar 2024 21:33:18 +0100 Subject: improve aho corasick --- string/string.tex | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'string/string.tex') diff --git a/string/string.tex b/string/string.tex index c36ec69..526faa2 100644 --- a/string/string.tex +++ b/string/string.tex @@ -49,16 +49,18 @@ \begin{algorithm}{\textsc{Aho-Corasick}-Automat} \begin{methods}[ll] - sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}+\abs{matches}} + sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}} \end{methods} \begin{enumerate} - \item mit \code{addString(pattern, idx);} Patterns hinzufügen. + \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 mit \code{state = getExit(state)} den exit Kanten folgen bis \code{state == 0} - \item dabei mit \code{aho[state].patterns} die Matches zählen + \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} -- cgit v1.2.3