From 961706d93af4daf58d5991deea88981a01f962b0 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 23 Aug 2024 21:36:51 +0200
Subject: more stuff

---
 content/string/duval.cpp | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

(limited to 'content/string')

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;
+}}
-- 
cgit v1.2.3


From 900d941a9cf28cdda8dbdb1e4fe2c0fe0dbe7682 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
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')

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;
-- 
cgit v1.2.3