diff options
| -rw-r--r-- | string/ahoCorasick.cpp | 66 | ||||
| -rw-r--r-- | string/string.tex | 10 |
2 files changed, 38 insertions, 38 deletions
diff --git a/string/ahoCorasick.cpp b/string/ahoCorasick.cpp index 9ffa6c9..eac312c 100644 --- a/string/ahoCorasick.cpp +++ b/string/ahoCorasick.cpp @@ -1,54 +1,52 @@ -constexpr ll ALPHABET_SIZE = 26; -constexpr char OFFSET = 'a'; +constexpr ll ALPHABET_SIZE = 26, OFFSET = 'a'; struct AhoCorasick { struct vert { - int suffix, exit, character, parent; - vector<int> nxt, patterns; - vert(int c, int p) : suffix(-1), exit(-1), - character(c), nxt(ALPHABET_SIZE, -1), parent(p) {} - }; - vector<vert> aho; + int suffix = 0, ch, cnt = 0; + array<int, ALPHABET_SIZE> nxt = {}; - AhoCorasick() {aho.push_back(vert(-1, 0));} + vert(int p, int c) : suffix(-p), ch(c) {} + }; + vector<vert> aho = {{0, -1}}; - // Call once for each pattern. - void addString(string &s, int patternIdx) { + int addString(string &s) { int v = 0; - for (char c : s) { + for (auto c : s) { int idx = c - OFFSET; - if (aho[v].nxt[idx] == -1) { + if (!aho[v].nxt[idx]) { aho[v].nxt[idx] = sz(aho); - aho.emplace_back(idx, v); + aho.emplace_back(v, idx); } v = aho[v].nxt[idx]; } - aho[v].patterns.push_back(patternIdx); + aho[v].cnt++; + return v; // trie node index of pattern (pattern state) } int getSuffix(int v) { - if (aho[v].suffix == -1) { - if (v == 0 || aho[v].parent == 0) aho[v].suffix = 0; - else aho[v].suffix = go(getSuffix(aho[v].parent), - aho[v].character); + if (aho[v].suffix < 0) { + aho[v].suffix = go(getSuffix(-aho[v].suffix), aho[v].ch); } return aho[v].suffix; } - int getExit(int v) { - if (aho[v].exit == -1) { - int suffix = getSuffix(v); - if (v == 0) aho[v].exit = 0; - else { - if (aho[suffix].patterns.empty()) { - aho[v].exit = getExit(suffix); - } else { - aho[v].exit = suffix; - }}} - return aho[v].exit; - } - - int go(int v, int idx) { // Root is v=0. - if (aho[v].nxt[idx] != -1) return aho[v].nxt[idx]; + int go(int v, int idx) { // Root is v=0, idx is char - OFFSET + if (aho[v].nxt[idx]) return aho[v].nxt[idx]; else return v == 0 ? 0 : go(getSuffix(v), idx); } + + vector<vector<int>> adj; + vector<ll> dp; + void buildGraph() { + adj.resize(sz(aho)); + dp.assign(sz(aho), 0); + for (int i = 1; i < sz(aho); i++) { + adj[getSuffix(i)].push_back(i); + }} + + void dfs(int v = 0) { // dp on tree + for (int u : adj[v]) { + //dp[u] = dp[v] + aho[u].cnt; // pattern count + dfs(u); + dp[v] += dp[u]; // no of matches + }} }; 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} |