summaryrefslogtreecommitdiff
path: root/test/string
diff options
context:
space:
mode:
Diffstat (limited to 'test/string')
-rw-r--r--test/string/ahoCorasick.cpp76
-rw-r--r--test/string/deBruijn.cpp43
-rw-r--r--test/string/duval.cpp85
-rw-r--r--test/string/kmp.cpp85
-rw-r--r--test/string/longestCommonSubsequence.cpp55
-rw-r--r--test/string/lyndon.cpp61
-rw-r--r--test/string/manacher.cpp49
-rw-r--r--test/string/rollingHash.cpp92
-rw-r--r--test/string/rollingHashCf.cpp94
-rw-r--r--test/string/suffixArray.cpp61
-rw-r--r--test/string/suffixAutomaton.cpp62
-rw-r--r--test/string/suffixTree.cpp50
-rw-r--r--test/string/trie.cpp58
-rw-r--r--test/string/z.cpp41
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();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 18:00:50 +0000