diff options
Diffstat (limited to 'content/string')
| -rw-r--r-- | content/string/ahoCorasick.cpp | 8 | ||||
| -rw-r--r-- | content/string/duval.cpp | 8 |
2 files changed, 7 insertions, 9 deletions
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<int, ALPHABET_SIZE> nxt = {}; - vert(int p, int c) : suffix(-p), ch(c) {} + vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);} }; vector<vert> 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<vector<int>> adj; diff --git a/content/string/duval.cpp b/content/string/duval.cpp index bf36cce..253bae1 100644 --- a/content/string/duval.cpp +++ b/content/string/duval.cpp @@ -6,9 +6,8 @@ vector<pair<int, int>> duval(const string& s) { if (s[k] < s[j]) k = i; else k++; } - while (i <= k) { + for (; i <= k; i += j - k) { res.push_back({i, i + j - k}); - i += j - k; }} return res; } @@ -16,6 +15,5 @@ vector<pair<int, int>> duval(const string& s) { int minrotation(const string& s) { auto parts = duval(s+s); for (auto [l, r] : parts) { - if (l < sz(s) && r >= sz(s)) { - return l; -}}} + if (r >= sz(s)) return l; +}} |