From 900d941a9cf28cdda8dbdb1e4fe2c0fe0dbe7682 Mon Sep 17 00:00:00 2001 From: Yidi Date: Wed, 11 Sep 2024 22:54:37 +0200 Subject: improve aho corasick --- content/string/ahoCorasick.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'content/string/ahoCorasick.cpp') diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp index eac312c..390d16d 100644 --- a/content/string/ahoCorasick.cpp +++ b/content/string/ahoCorasick.cpp @@ -4,7 +4,7 @@ struct AhoCorasick { int suffix = 0, ch, cnt = 0; array nxt = {}; - vert(int p, int c) : suffix(-p), ch(c) {} + vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);} }; vector aho = {{0, -1}}; @@ -12,7 +12,7 @@ struct AhoCorasick { int v = 0; for (auto c : s) { int idx = c - OFFSET; - if (!aho[v].nxt[idx]) { + if (aho[v].nxt[idx] == -1) { aho[v].nxt[idx] = sz(aho); aho.emplace_back(v, idx); } @@ -30,8 +30,8 @@ struct AhoCorasick { } 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); + if (aho[v].nxt[idx] != -1) return aho[v].nxt[idx]; + return v == 0 ? 0 : aho[v].nxt[idx] = go(getSuffix(v), idx); } vector> adj; -- cgit v1.2.3