mzuenni tests

14 files changed, 912 insertions, 0 deletions

diff --git a/test/string/ahoCorasick.cpp b/test/string/ahoCorasick.cpp
new file mode 100644
index 0000000..c3361d6
--- /dev/null
+++ b/test/string/ahoCorasick.cpp
@@ -0,0 +1,76 @@
+#include "../util.h"
+#include <string/ahoCorasick.cpp>
+
+vector<ll> naive(string s, vector<string> patterns) {
+    vector<ll> ans(patterns.size());
+    for (int k = 0; k < (int)patterns.size(); k++) {
+        string pattern = patterns[k];
+        for (int i = 0; i + pattern.size() <= s.size(); i++) {
+            if (s.substr(i, pattern.size()) == pattern) ans[k]++;
+        }
+    }
+    return ans;
+}
+
+vector<ll> normal(string s, vector<string> patterns) {
+    AhoCorasick aho;
+    vector<int> ind(patterns.size());
+    for (int i = 0; i < (int)patterns.size(); i++) {
+        ind[i] = aho.addString(patterns[i]);
+    }
+    aho.buildGraph();
+
+    int v = 0;
+    for (char c : s) v = aho.go(v, c - OFFSET), aho.dp[v]++;
+    aho.dfs();
+    vector<ll> ans(patterns.size());
+    for (int i = 0; i < (int)patterns.size(); i++) {
+        ans[i] = aho.dp[ind[i]];
+    }
+    return ans;
+}
+
+void stress_test() {
+    ll queries = 0;
+    for (int i = 0; i < 100; i++) {
+        int n = Random::integer(1, 100);
+        string s = Random::string(n, "abc");
+        int m = Random::integer(1, 100);
+        vector<string> patterns(m);
+        for (string& e : patterns) {
+            int k = Random::integer(1, 100);
+            e = Random::string(k, "abc");
+        }
+
+        auto got = normal(s, patterns);
+        auto expected = naive(s, patterns);
+        if (got != expected) cerr << "Wrong Answer" << FAIL;
+        queries++;
+    }
+    cerr << "Tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+    timer t;
+    string s = string(N, 'a') + Random::string(N, "ab");
+    vector<string> patterns = {"a"};
+    for (int sm = 1; sm < N; sm += patterns.back().size()) {
+        patterns.emplace_back(patterns.back().size()+1, 'a');
+    }
+    for (int i = 0; i < 100; i++) {
+        patterns.emplace_back(Random::string(N/100, "ab"));
+    }
+
+    t.start();
+    hash_t hash = normal(s, patterns)[0];
+    t.stop();
+
+    if (t.time > 500) cerr << "Too slow: " << t.time << FAIL;
+    cerr << "Tested performance: " << t.time << "ms (hash: hash " << hash << ")" << endl;
+}
+
+int main() {
+    stress_test();
+    performance_test();
+}
diff --git a/test/string/deBruijn.cpp b/test/string/deBruijn.cpp
new file mode 100644
index 0000000..6b3fea4
--- /dev/null
+++ b/test/string/deBruijn.cpp
@@ -0,0 +1,43 @@
+#include "../util.h"
+#include <string/lyndon.cpp>
+#include <string/deBruijn.cpp>
+
+bool isDeBruijn(string s, int n, int k) {
+	ll expected = 1;
+	for (ll i = 0; i < n; i++) expected *= k;
+	if (expected != sz(s)) return false;
+	s += s;
+	set<string_view> seen;
+	for (ll i = 0; 2*i < sz(s); i++) {
+		seen.insert(string_view(s).substr(i, n));
+	}
+	return sz(seen) == expected;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 1000; i++) {
+		int n = Random::integer<int>(1, 9);
+		auto [l, r] = Random::pair<char>('b', 'f');
+		auto got = deBruijn(n, l, r);
+		if (!isDeBruijn(got, n, r - l + 1)) cerr << "error" << FAIL;
+		queries += sz(got);
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 26;
+void performance_test() {
+	timer t;
+	t.start();
+	auto res = deBruijn(N, '0', '1');
+	t.stop();
+	hash_t hash = sz(res);
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/duval.cpp b/test/string/duval.cpp
new file mode 100644
index 0000000..58b4a44
--- /dev/null
+++ b/test/string/duval.cpp
@@ -0,0 +1,85 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wreturn-type"
+#include <string/duval.cpp>
+
+constexpr int N = 20'000'000;
+
+bool isLyndon(string_view s) {
+	string t = string(s) + string(s);
+	for (ll i = 1; i < sz(s); i++) {
+		if (s >= t.substr(i, sz(s))) return false;
+	}
+	return !s.empty();
+}
+
+void stress_test_duval() {
+	ll queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		auto s = Random::string(n, "abc");
+		vector<pair<int, int>> got = duval(s);
+		if (got.empty()) cerr << "error: a" << FAIL;
+		if (got.front().first != 0) cerr << "error: b" << FAIL;
+		if (got.back().second != n) cerr << "error: c" << FAIL;
+		for (int j = 1; j < sz(got); j++) {
+			if (got[j - 1].second != got[j].first) cerr << "error: d" << FAIL; 
+		}
+		for (auto [l, r] : got) {
+			if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL; 
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void performance_test_duval() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	auto got = duval(s);
+	t.stop();
+	hash_t hash = 0;
+	for (auto [l, r] : got) hash += l + r;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int naive(string s) {
+	ll n = sz(s);
+	s += s;
+	int res = 0;
+	for (int i = 0; i < n; i++) {
+		if (string_view(s).substr(i, n) <= string_view(s).substr(res, n)) res = i;
+	}
+	return res;
+}
+
+void stress_test_minrotation() {
+	ll queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		auto s = Random::string(n, "abc");
+		int got = minrotation(s);
+		auto expected = naive(s);
+		if (got != expected) cerr << s << ": got: " << got << ", expected: " << expected << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void performance_test_minrotation() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	hash_t hash = minrotation(s);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test_duval();
+	performance_test_duval();
+	stress_test_minrotation();
+	performance_test_minrotation();
+}
diff --git a/test/string/kmp.cpp b/test/string/kmp.cpp
new file mode 100644
index 0000000..9c9c924
--- /dev/null
+++ b/test/string/kmp.cpp
@@ -0,0 +1,85 @@
+#include "../util.h"
+#include <string/kmp.cpp>
+
+vector<int> naive(string_view s) {
+	vector<int> res(sz(s) + 1, -1);
+	for (int i = 0; i < sz(s); i++) {
+		for (int j = 0; j <= i; j++)
+			if (s.substr(0, j) == s.substr(i-j+1, j))
+				res[i+1] = j;
+	}
+	return res;
+}
+
+void stress_test_preprocessing() {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 15);
+		auto s = Random::string(n, "abc");
+		auto got = kmpPreprocessing(s);
+		auto expected = naive(s);
+		if (got != expected) cerr << "  error" << FAIL;
+		queries += n;
+	}
+	cerr << "  tested random queries: " << queries << endl;
+}
+
+constexpr int N = 10'000'000;
+void performance_test_preprocessing() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	auto res = kmpPreprocessing(s);
+	t.stop();
+	hash_t hash = 0;
+	for (int x : res) hash += x;
+	if (t.time > 500) cerr << "  too slow: " << t.time << FAIL;
+	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+vector<int> naive(string_view s, string_view sub) {
+	vector<int> res;
+	auto pos = s.find(sub);
+	while (pos != string_view::npos) {
+		res.push_back(pos);
+		pos = s.find(sub, pos + 1);
+	}
+	return res;
+}
+
+void stress_test_kmp() {
+	ll queries = 0;
+	auto a = Random::string(10'000, "abc");
+	for (int tries = 0; tries < 10'000; tries++) {
+		int n = Random::integer<int>(1, 10);
+		auto b = Random::string(n, "abc");
+		auto got = kmpSearch(a, b);
+		auto expected = naive(a, b);
+		if (got != expected) cerr << "  error" << FAIL;
+		queries += got.size();
+	}
+	cerr << "  tested random queries: " << queries << endl;
+}
+
+void performance_test_kmp() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	auto sub1 = Random::string(N/2, "a");
+	auto sub2 = Random::string(N/2, "ab");
+	hash_t hash = 0;
+	t.start();
+	hash += kmpSearch(s, sub1).size();
+	hash += kmpSearch(s, sub2).size();
+	t.stop();
+	if (t.time > 500) cerr << "  too slow: " << t.time << FAIL;
+	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	cerr << "preprocessing:" << endl;
+	stress_test_preprocessing();
+	performance_test_preprocessing();
+	cerr << "kmp:" << endl;
+	stress_test_kmp();
+	performance_test_kmp();
+}
diff --git a/test/string/longestCommonSubsequence.cpp b/test/string/longestCommonSubsequence.cpp
new file mode 100644
index 0000000..6d7a6c5
--- /dev/null
+++ b/test/string/longestCommonSubsequence.cpp
@@ -0,0 +1,55 @@
+#include "../util.h"
+#include <string/longestCommonSubsequence.cpp>
+
+bool isSubstr(string_view s, string_view sub) {
+	int i = 0;
+	for (char c : s) {
+		if (i < sz(sub) && c == sub[i]) i++;
+	}
+	return i >= sz(sub);
+}
+
+string naive(string_view s, string_view t) {
+	string res = "";
+	for (ll i = 1; i < (1ll << sz(s)); i++) {
+		string tmp;
+		for (ll j = 0; j < sz(s); j++) {
+			if (((i >> j) & 1) != 0) tmp.push_back(s[j]);
+		}
+		if (sz(tmp) >= sz(res) && isSubstr(t, tmp)) res = tmp;
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 12);
+		int m = Random::integer<int>(1, 12);
+		auto s = Random::string(n, "abc");
+		auto t = Random::string(m, "abc");
+		auto got = lcss(s, t);
+		auto expected = naive(s, t);
+		if (got != expected) cerr << s << ", " << t << ", got: " << got << ", expected: " << expected << FAIL;
+		queries += n + m;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 2'000;
+void performance_test() {
+	timer t;
+	auto a = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	auto b = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	auto res = lcss(a, b);
+	t.stop();
+	hash_t hash = sz(res);
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/lyndon.cpp b/test/string/lyndon.cpp
new file mode 100644
index 0000000..ecf2dad
--- /dev/null
+++ b/test/string/lyndon.cpp
@@ -0,0 +1,61 @@
+#include "../util.h"
+#include <string/lyndon.cpp>
+
+bool isLyndon(string_view s) {
+	string t = string(s) + string(s);
+	for (ll i = 1; i < sz(s); i++) {
+		if (s >= t.substr(i, sz(s))) return false;
+	}
+	return !s.empty();
+}
+
+vector<string> naive(ll n, char mi, char ma) {
+	vector<string> res;
+	auto dfs = [&](auto&& self, string pref)->void{
+		if (sz(pref) <= n && isLyndon(pref)) res.push_back(pref);
+		if (sz(pref) >= n) return;
+		for (char c = mi; c <= ma; c++) {
+			self(self, pref + c);
+		}
+	};
+	dfs(dfs, "");
+	return res;
+}
+
+vector<string> fast(ll n, char mi, char ma) {
+	vector<string> res;
+	string tmp(1, mi);
+	do {
+		res.push_back(tmp);
+	} while (next(tmp, n, mi, ma));
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 6);
+		auto [l, r] = Random::pair<char>('a', 'f');
+		auto got = fast(n, l, r);
+		auto expected = naive(n, l, r);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += sz(expected);
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 9;
+void performance_test() {
+	timer t;
+	t.start();
+	auto res = fast(N, 'a', 'f');
+	t.stop();
+	hash_t hash = sz(res);
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/manacher.cpp b/test/string/manacher.cpp
new file mode 100644
index 0000000..503d181
--- /dev/null
+++ b/test/string/manacher.cpp
@@ -0,0 +1,49 @@
+#include "../util.h"
+#include <string/manacher.cpp>
+
+vector<int> naive(string_view s) {
+	vector<int> res(2 * sz(s) + 1);
+	for (int i = 0; i < sz(s); i++) { //odd palindromes
+		int j = 2*i+1;
+		while (i+res[j] < sz(s) && i-res[j] >= 0 && s[i-res[j]] == s[i+res[j]]) res[j]++;
+		res[j]*=2;
+		res[j]--;
+	}
+	for (int i = 0; i <= sz(s); i++) { //even palindromes
+		int j = 2*i;
+		while (i+res[j] < sz(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++;
+		res[j] *= 2;
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		auto s = Random::string(n, "abc");
+		vector<int> got = manacher(s);
+		vector<int> expected = naive(s);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 5'000'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	auto got = manacher(s);
+	t.stop();
+	hash_t hash = 0;
+	for (int x : got) hash += x;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/rollingHash.cpp b/test/string/rollingHash.cpp
new file mode 100644
index 0000000..0491bc0
--- /dev/null
+++ b/test/string/rollingHash.cpp
@@ -0,0 +1,92 @@
+#include "../util.h"
+#include <string/rollingHash.cpp>
+
+string thueMorse(ll n) {
+	string res = "a";
+	while (sz(res) < n) {
+		string tmp = res;
+		for (char& c : tmp) c ^= 1;
+		res += tmp;
+	}
+	return res;
+}
+
+auto getHash(const string& s) {
+	return Hash(s)(0, sz(s));
+}
+
+void testThueMorse() {
+	set<decltype(getHash(""))> got;
+	set<string> expected;
+	string s = thueMorse(1000);
+	Hash h(s);
+	for (int l = 0; l < sz(s); l++) {
+		for (int r = l + 1; r <= sz(s); r++) {
+			got.insert(h(l, r));
+			expected.insert(s.substr(l, r - l));
+		}
+	}
+	if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL;
+	cerr << "thueMorse: ok" << endl;
+}
+
+void testTiny() {
+	if (getHash("aa") == getHash("a")) cerr << "error: tiny" << FAIL;
+	if (getHash("00") == getHash("0")) cerr << "error: tiny" << FAIL;
+	if (getHash("AA") == getHash("A")) cerr << "error: tiny" << FAIL;
+	cerr << "tiny: ok" << endl;
+}
+
+void testSmall() {
+	set<decltype(getHash(""))> got;
+	ll expected = 0;
+	auto dfs = [&](auto&& self, string pref)->void {
+		expected++;
+		got.insert(getHash(pref));
+		if(sz(pref) >= 5) return;
+		for (char c = 'a'; c <= 'z'; c++) {
+			self(self, pref + c);
+		}
+	};
+	dfs(dfs, "");
+	if (sz(got) != expected) cerr << "error: small" << FAIL;
+	cerr << "small: ok" << endl;
+}
+
+void stress_test() {
+	set<decltype(getHash(""))> got;
+	set<string> expected;
+	string s = Random::string(1000, "abc");
+	Hash h(s);
+	for (int l = 0; l < sz(s); l++) {
+		for (int r = l + 1; r <= sz(s); r++) {
+			got.insert(h(l, r));
+			expected.insert(s.substr(l, r - l));
+		}
+	}
+	if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL;
+	cerr << "stress test: ok" << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	hash_t hash = 0;
+	t.start();
+	Hash h(s);
+	for (ll i = 0; i < N; i++) {
+		hash += h(i, i + 2*N);
+	}
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	testThueMorse();
+	testTiny();
+	testSmall();
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/rollingHashCf.cpp b/test/string/rollingHashCf.cpp
new file mode 100644
index 0000000..79003de
--- /dev/null
+++ b/test/string/rollingHashCf.cpp
@@ -0,0 +1,94 @@
+#include "../util.h"
+#include <string/rollingHashCf.cpp>
+
+constexpr ll RandomQ = 318LL << 53;
+
+string thueMorse(ll n) {
+	string res = "a";
+	while (sz(res) < n) {
+		string tmp = res;
+		for (char& c : tmp) c ^= 1;
+		res += tmp;
+	}
+	return res;
+}
+
+auto getHash(const string& s) {
+	return Hash(s, RandomQ)(0, sz(s));
+}
+
+void testThueMorse() {
+	set<decltype(getHash(""))> got;
+	set<string> expected;
+	string s = thueMorse(1000);
+	Hash h(s, RandomQ);
+	for (int l = 0; l < sz(s); l++) {
+		for (int r = l + 1; r <= sz(s); r++) {
+			got.insert(h(l, r));
+			expected.insert(s.substr(l, r - l));
+		}
+	}
+	if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL;
+	cerr << "thueMorse: ok" << endl;
+}
+
+void testTiny() {
+	if (getHash("aa") == getHash("a")) cerr << "error: tiny" << FAIL;
+	if (getHash("00") == getHash("0")) cerr << "error: tiny" << FAIL;
+	if (getHash("AA") == getHash("A")) cerr << "error: tiny" << FAIL;
+	cerr << "tiny: ok" << endl;
+}
+
+void testSmall() {
+	set<decltype(getHash(""))> got;
+	ll expected = 0;
+	auto dfs = [&](auto&& self, string pref)->void {
+		expected++;
+		got.insert(getHash(pref));
+		if(sz(pref) >= 5) return;
+		for (char c = 'a'; c <= 'z'; c++) {
+			self(self, pref + c);
+		}
+	};
+	dfs(dfs, "");
+	if (sz(got) != expected) cerr << "error: small" << FAIL;
+	cerr << "small: ok" << endl;
+}
+
+void stress_test() {
+	set<decltype(getHash(""))> got;
+	set<string> expected;
+	string s = Random::string(1000, "abc");
+	Hash h(s, RandomQ);
+	for (int l = 0; l < sz(s); l++) {
+		for (int r = l + 1; r <= sz(s); r++) {
+			got.insert(h(l, r));
+			expected.insert(s.substr(l, r - l));
+		}
+	}
+	if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL;
+	cerr << "stress test: ok" << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	hash_t hash = 0;
+	t.start();
+	Hash h(s, RandomQ);
+	for (ll i = 0; i < N; i++) {
+		hash += h(i, i + 2*N);
+	}
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	testThueMorse();
+	testTiny();
+	testSmall();
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/suffixArray.cpp b/test/string/suffixArray.cpp
new file mode 100644
index 0000000..4945d8e
--- /dev/null
+++ b/test/string/suffixArray.cpp
@@ -0,0 +1,61 @@
+#include "../util.h"
+#include <string/suffixArray.cpp>
+
+vector<int> naive(string_view s) {
+	vector<int> SA(sz(s));
+	iota(all(SA), 0);
+	sort(all(SA), [s](int a, int b){
+		return s.substr(a) < s.substr(b);
+	});
+	return SA;
+}
+
+int lcp(string_view s, int x, int y) {
+	int res = 0;
+	while (x + res < sz(s) && y + res < sz(s) && s[x + res] == s[y + res]) res++;
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int i = 0; i < 100; i++) {
+		int n = Random::integer<int>(1, 100);
+		auto s = Random::string(n, "abc");
+		SuffixArray sa(s);
+		vector<int> got = sa.SA;
+		vector<int> expected = naive(s);
+		vector<int> SA(n);
+		if (got != expected) cerr << "error: SA" << FAIL;
+		got = sa.LCP;
+		swap(SA, expected);
+		for (int x = 0; x < n; x++) {
+			for (int y = 0; y < n; y++) {
+				int gotLCP = sa.lcp(x, y);
+				int expectedLCP = lcp(s, x, y);
+				if (gotLCP != expectedLCP) cerr << "error: lcp" << FAIL;
+			}
+			if (x > 0) expected[x] = lcp(s, SA[x-1], SA[x]);
+		}
+		if (got != expected) cerr << "error: LCP" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	SuffixArray sa(s);
+	t.stop();
+	hash_t hash = 0;
+	for (int i = 0; i < sz(sa.SA); i++) hash += i*sa.SA[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/suffixAutomaton.cpp b/test/string/suffixAutomaton.cpp
new file mode 100644
index 0000000..c2ff511
--- /dev/null
+++ b/test/string/suffixAutomaton.cpp
@@ -0,0 +1,62 @@
+#include "../util.h"
+#include <string/suffixAutomaton.cpp>
+
+pair<int, int> naive(string_view s, string_view t) {
+	int pos = 0;
+	int len = 0;
+	for (int j = 0; j < sz(t); j++) {
+		for (int i = 0; i < sz(s); i++) {
+			int cur = 0;
+			while (i+cur < sz(s) && j+cur < sz(t) && s[i+cur] == t[j+cur]) cur++;
+			if (cur > len) {
+				pos = j;
+				len = cur;
+			}
+		}
+	}
+	return {pos, len};
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int i = 0; i < 1000; i++) {
+		int n = Random::integer<int>(1, 100);
+		auto s = Random::string(n, "abc");
+		SuffixAutomaton sa(s);
+		for (int j = 0; j < 1000; j++) {
+			int m = Random::integer<int>(1, 100);
+			auto t = Random::string(m, "abc");
+			auto got = sa.longestCommonSubstring(t);
+			auto expected = naive(s, t);
+			if (got != expected) cerr << "error" << FAIL;
+			queries += m;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 500'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyz");
+	t.start();
+	SuffixAutomaton sa(s);
+	t.stop();
+	hash_t hash = 0;
+	for (ll c = 0; c < sz(s);) {
+		int m = Random::integer<int>(1, 1000);
+		s = Random::string(m, "abc");
+		t.start();
+		auto [p, l] = sa.longestCommonSubstring(s);
+		t.stop();
+		hash += l + p;
+		c += m;
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/suffixTree.cpp b/test/string/suffixTree.cpp
new file mode 100644
index 0000000..c0d79e4
--- /dev/null
+++ b/test/string/suffixTree.cpp
@@ -0,0 +1,50 @@
+#include "../util.h"
+#include <string/suffixTree.cpp>
+
+vector<string> naive(string_view s) {
+	vector<string> res(sz(s));
+	for (ll i = 0; i < sz(s); i++) {
+		res[i] = s.substr(i);
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 15);
+		auto s = Random::string(n, "abc") + "#";
+		SuffixTree st(s);
+		vector<string> got(n + 1);
+		auto dfs = [&](auto&& self, string pref, ll node) -> void {
+			auto& [l, r, _, next] = st.tree[node];
+			if (l >= 0) pref += s.substr(l, r - l);
+			if (pref.back() == '#') got[n + 1 - sz(pref)] = pref;
+			for (auto [__, j] : next) {
+				self(self, pref, j);
+			}
+		};
+		dfs(dfs, "", 0);
+		auto expected = naive(s);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	SuffixTree st(s);
+	t.stop();
+	hash_t hash = sz(st.tree);
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/trie.cpp b/test/string/trie.cpp
new file mode 100644
index 0000000..45d89cf
--- /dev/null
+++ b/test/string/trie.cpp
@@ -0,0 +1,58 @@
+#include "../util.h"
+#include <string/trie.cpp>
+
+void stress_test() {
+	multiset<vector<int>> naive;
+	ll queries = 0;
+	ll deleted = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		{
+			int n = Random::integer<int>(1, 20);
+			auto s = Random::integers<int>(n, 0, 2);
+			insert(s);
+			naive.insert(s);
+		}
+		{
+			int n = Random::integer<int>(1, 20);
+			auto s = Random::integers<int>(n, 0, 2);
+			bool got = erase(s);
+			auto it = naive.find(s);
+			bool expected = it != naive.end();
+			if (expected) naive.erase(it);
+			if (got != expected) cerr << "error" << FAIL;
+			queries++;
+			if (got) deleted++;
+		}
+	}
+	cerr << "tested random queries: " << queries << " (" << deleted << ")" << endl;
+}
+
+constexpr int N = 10'000;
+void performance_test() {
+	timer t;
+	trie = {node()};
+	hash_t hash = 0;
+	for (int tries = 0; tries < N; tries++) {
+		{
+			int n = Random::integer<int>(1, 2000);
+			auto s = Random::integers<int>(n, 0, 2);
+			t.start();
+			insert(s);
+			t.stop();
+		}
+		{
+			int n = Random::integer<int>(1, 2000);
+			auto s = Random::integers<int>(n, 0, 2);
+			t.start();
+			hash += erase(s);
+			t.stop();
+		}
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/string/z.cpp b/test/string/z.cpp
new file mode 100644
index 0000000..f890a3e
--- /dev/null
+++ b/test/string/z.cpp
@@ -0,0 +1,41 @@
+#include "../util.h"
+#include <string/z.cpp>
+
+vector<int> naive(const string& s) {
+	vector<int> res(sz(s));
+	for (int i = 1; i < sz(s); i++) {
+		while (i + res[i] < sz(s) && s[res[i]] == s[i + res[i]]) res[i]++;
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 15);
+		auto s = Random::string(n, "abc");
+		auto got = Z(s);
+		auto expected = naive(s);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 10'000'000;
+void performance_test() {
+	timer t;
+	auto s = Random::string(N, "a") + Random::string(N, "ab") + Random::string(N, "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#");
+	t.start();
+	auto res = Z(s);
+	t.stop();
+	hash_t hash = 0;
+	for (int x : res) hash += x;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}