summaryrefslogtreecommitdiff
path: root/test/string
diff options
context:
space:
mode:
Diffstat (limited to 'test/string')
-rw-r--r--test/string/deBruijn.cpp10
-rw-r--r--test/string/duval.cpp12
-rw-r--r--test/string/kmp.cpp4
-rw-r--r--test/string/longestCommonSubsequence.cpp12
-rw-r--r--test/string/lyndon.cpp12
-rw-r--r--test/string/manacher.cpp10
-rw-r--r--test/string/rollingHash.cpp20
-rw-r--r--test/string/rollingHashCf.cpp20
-rw-r--r--test/string/suffixArray.cpp10
-rw-r--r--test/string/suffixAutomaton.cpp8
-rw-r--r--test/string/suffixTree.cpp8
-rw-r--r--test/string/z.cpp6
12 files changed, 66 insertions, 66 deletions
diff --git a/test/string/deBruijn.cpp b/test/string/deBruijn.cpp
index 09ba611..6bbbad9 100644
--- a/test/string/deBruijn.cpp
+++ b/test/string/deBruijn.cpp
@@ -5,13 +5,13 @@
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;
+ if (expected != ssize(s)) return false;
s += s;
set<string_view> seen;
- for (ll i = 0; 2*i < sz(s); i++) {
+ for (ll i = 0; 2*i < ssize(s); i++) {
seen.insert(string_view(s).substr(i, n));
}
- return sz(seen) == expected;
+ return ssize(seen) == expected;
}
void stress_test() {
@@ -21,7 +21,7 @@ void stress_test() {
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);
+ queries += ssize(got);
}
cerr << "tested random queries: " << queries << endl;
}
@@ -32,7 +32,7 @@ void performance_test() {
t.start();
auto res = deBruijn(N, '0', '1');
t.stop();
- hash_t hash = sz(res);
+ hash_t hash = ssize(res);
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/string/duval.cpp b/test/string/duval.cpp
index 0475386..88e2fb7 100644
--- a/test/string/duval.cpp
+++ b/test/string/duval.cpp
@@ -6,8 +6,8 @@ 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;
+ for (ll i = 1; i < ssize(s); i++) {
+ if (s >= t.substr(i, ssize(s))) return false;
}
return !s.empty();
}
@@ -21,11 +21,11 @@ void stress_test_duval() {
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 (int j = 1; j < ssize(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;
+ if (!isLyndon(string_view(s).substr(l, r-l))) cerr << "error: e" << FAIL;
}
queries += n;
}
@@ -45,7 +45,7 @@ void performance_test_duval() {
}
int naive(string s) {
- ll n = sz(s);
+ ll n = ssize(s);
s += s;
int res = 0;
for (int i = 0; i < n; i++) {
diff --git a/test/string/kmp.cpp b/test/string/kmp.cpp
index f70a887..8ebeb64 100644
--- a/test/string/kmp.cpp
+++ b/test/string/kmp.cpp
@@ -2,8 +2,8 @@
#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++) {
+ vector<int> res(ssize(s) + 1, -1);
+ for (int i = 0; i < ssize(s); i++) {
for (int j = 0; j <= i; j++)
if (s.substr(0, j) == s.substr(i-j+1, j))
res[i+1] = j;
diff --git a/test/string/longestCommonSubsequence.cpp b/test/string/longestCommonSubsequence.cpp
index 68ec71b..8c32d61 100644
--- a/test/string/longestCommonSubsequence.cpp
+++ b/test/string/longestCommonSubsequence.cpp
@@ -4,19 +4,19 @@
bool isSubstr(string_view s, string_view sub) {
int i = 0;
for (char c : s) {
- if (i < sz(sub) && c == sub[i]) i++;
+ if (i < ssize(sub) && c == sub[i]) i++;
}
- return i >= sz(sub);
+ return i >= ssize(sub);
}
string naive(string_view s, string_view t) {
string res = "";
- for (ll i = 1; i < (1ll << sz(s)); i++) {
+ for (ll i = 1; i < (1ll << ssize(s)); i++) {
string tmp;
- for (ll j = 0; j < sz(s); j++) {
+ for (ll j = 0; j < ssize(s); j++) {
if (((i >> j) & 1) != 0) tmp.push_back(s[j]);
}
- if (sz(tmp) >= sz(res) && isSubstr(t, tmp)) res = tmp;
+ if (ssize(tmp) >= ssize(res) && isSubstr(t, tmp)) res = tmp;
}
return res;
}
@@ -44,7 +44,7 @@ void performance_test() {
t.start();
auto res = lcss(a, b);
t.stop();
- hash_t hash = sz(res);
+ hash_t hash = ssize(res);
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/string/lyndon.cpp b/test/string/lyndon.cpp
index 905bf8e..154ba66 100644
--- a/test/string/lyndon.cpp
+++ b/test/string/lyndon.cpp
@@ -3,8 +3,8 @@
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;
+ for (ll i = 1; i < ssize(s); i++) {
+ if (s >= t.substr(i, ssize(s))) return false;
}
return !s.empty();
}
@@ -12,8 +12,8 @@ bool isLyndon(string_view s) {
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;
+ if (ssize(pref) <= n && isLyndon(pref)) res.push_back(pref);
+ if (ssize(pref) >= n) return;
for (char c = mi; c <= ma; c++) {
self(self, pref + c);
}
@@ -39,7 +39,7 @@ void stress_test() {
auto got = fast(n, l, r);
auto expected = naive(n, l, r);
if (got != expected) cerr << "error" << FAIL;
- queries += sz(expected);
+ queries += ssize(expected);
}
cerr << "tested random queries: " << queries << endl;
}
@@ -50,7 +50,7 @@ void performance_test() {
t.start();
auto res = fast(N, 'a', 'f');
t.stop();
- hash_t hash = sz(res);
+ hash_t hash = ssize(res);
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/string/manacher.cpp b/test/string/manacher.cpp
index bde1c89..ada0486 100644
--- a/test/string/manacher.cpp
+++ b/test/string/manacher.cpp
@@ -2,16 +2,16 @@
#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
+ vector<int> res(2 * ssize(s) + 1);
+ for (int i = 0; i < ssize(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]++;
+ while (i+res[j] < ssize(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
+ for (int i = 0; i <= ssize(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]++;
+ while (i+res[j] < ssize(s) && i-res[j]-1 >= 0 && s[i-res[j]-1] == s[i+res[j]]) res[j]++;
res[j] *= 2;
}
return res;
diff --git a/test/string/rollingHash.cpp b/test/string/rollingHash.cpp
index ba8fc40..d19a153 100644
--- a/test/string/rollingHash.cpp
+++ b/test/string/rollingHash.cpp
@@ -3,7 +3,7 @@
string thueMorse(ll n) {
string res = "a";
- while (sz(res) < n) {
+ while (ssize(res) < n) {
string tmp = res;
for (char& c : tmp) c ^= 1;
res += tmp;
@@ -12,7 +12,7 @@ string thueMorse(ll n) {
}
auto getHash(const string& s) {
- return Hash(s)(0, sz(s));
+ return Hash(s)(0, ssize(s));
}
void testThueMorse() {
@@ -20,13 +20,13 @@ void testThueMorse() {
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++) {
+ for (int l = 0; l < ssize(s); l++) {
+ for (int r = l + 1; r <= ssize(s); r++) {
got.insert(h(l, r));
expected.insert(s.substr(l, r - l));
}
}
- if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL;
+ if (ssize(got) != ssize(expected)) cerr << "error: thueMorse" << FAIL;
cerr << "thueMorse: ok" << endl;
}
@@ -43,13 +43,13 @@ void testSmall(int depth) {
auto dfs = [&](auto&& self, string pref)->void {
expected++;
got.insert(getHash(pref));
- if(sz(pref) >= depth) return;
+ if(ssize(pref) >= depth) return;
for (char c = 'a'; c <= 'z'; c++) {
self(self, pref + c);
}
};
dfs(dfs, "");
- if (sz(got) != expected) cerr << "error: small" << FAIL;
+ if (ssize(got) != expected) cerr << "error: small" << FAIL;
cerr << "small: ok" << endl;
}
@@ -58,13 +58,13 @@ void stress_test() {
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++) {
+ for (int l = 0; l < ssize(s); l++) {
+ for (int r = l + 1; r <= ssize(s); r++) {
got.insert(h(l, r));
expected.insert(s.substr(l, r - l));
}
}
- if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL;
+ if (ssize(got) != ssize(expected)) cerr << "error: stress test" << FAIL;
cerr << "stress test: ok" << endl;
}
diff --git a/test/string/rollingHashCf.cpp b/test/string/rollingHashCf.cpp
index 9acce2d..d0f90aa 100644
--- a/test/string/rollingHashCf.cpp
+++ b/test/string/rollingHashCf.cpp
@@ -5,7 +5,7 @@ constexpr ll RandomQ = 318LL << 53;
string thueMorse(ll n) {
string res = "a";
- while (sz(res) < n) {
+ while (ssize(res) < n) {
string tmp = res;
for (char& c : tmp) c ^= 1;
res += tmp;
@@ -14,7 +14,7 @@ string thueMorse(ll n) {
}
auto getHash(const string& s) {
- return Hash(s, RandomQ)(0, sz(s));
+ return Hash(s, RandomQ)(0, ssize(s));
}
void testThueMorse() {
@@ -22,13 +22,13 @@ void testThueMorse() {
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++) {
+ for (int l = 0; l < ssize(s); l++) {
+ for (int r = l + 1; r <= ssize(s); r++) {
got.insert(h(l, r));
expected.insert(s.substr(l, r - l));
}
}
- if (sz(got) != sz(expected)) cerr << "error: thueMorse" << FAIL;
+ if (ssize(got) != ssize(expected)) cerr << "error: thueMorse" << FAIL;
cerr << "thueMorse: ok" << endl;
}
@@ -45,13 +45,13 @@ void testSmall(int depth) {
auto dfs = [&](auto&& self, string pref)->void {
expected++;
got.insert(getHash(pref));
- if(sz(pref) >= depth) return;
+ if(ssize(pref) >= depth) return;
for (char c = 'a'; c <= 'z'; c++) {
self(self, pref + c);
}
};
dfs(dfs, "");
- if (sz(got) != expected) cerr << "error: small" << FAIL;
+ if (ssize(got) != expected) cerr << "error: small" << FAIL;
cerr << "small: ok" << endl;
}
@@ -60,13 +60,13 @@ void stress_test() {
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++) {
+ for (int l = 0; l < ssize(s); l++) {
+ for (int r = l + 1; r <= ssize(s); r++) {
got.insert(h(l, r));
expected.insert(s.substr(l, r - l));
}
}
- if (sz(got) != sz(expected)) cerr << "error: stress test" << FAIL;
+ if (ssize(got) != ssize(expected)) cerr << "error: stress test" << FAIL;
cerr << "stress test: ok" << endl;
}
diff --git a/test/string/suffixArray.cpp b/test/string/suffixArray.cpp
index 1314155..37049f6 100644
--- a/test/string/suffixArray.cpp
+++ b/test/string/suffixArray.cpp
@@ -2,9 +2,9 @@
#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){
+ vector<int> SA(ssize(s));
+ iota(begin(SA), end(SA), 0);
+ ranges::sort(SA, [s](int a, int b){
return s.substr(a) < s.substr(b);
});
return SA;
@@ -12,7 +12,7 @@ vector<int> naive(string_view s) {
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++;
+ while (x + res < ssize(s) && y + res < ssize(s) && s[x + res] == s[y + res]) res++;
return res;
}
@@ -50,7 +50,7 @@ void performance_test() {
SuffixArray sa(s);
t.stop();
hash_t hash = 0;
- for (int i = 0; i < sz(sa.SA); i++) hash += i*sa.SA[i];
+ for (int i = 0; i < ssize(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;
}
diff --git a/test/string/suffixAutomaton.cpp b/test/string/suffixAutomaton.cpp
index 146ae11..dacbb83 100644
--- a/test/string/suffixAutomaton.cpp
+++ b/test/string/suffixAutomaton.cpp
@@ -4,10 +4,10 @@
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++) {
+ for (int j = 0; j < ssize(t); j++) {
+ for (int i = 0; i < ssize(s); i++) {
int cur = 0;
- while (i+cur < sz(s) && j+cur < sz(t) && s[i+cur] == t[j+cur]) cur++;
+ while (i+cur < ssize(s) && j+cur < ssize(t) && s[i+cur] == t[j+cur]) cur++;
if (cur > len) {
pos = j;
len = cur;
@@ -43,7 +43,7 @@ void performance_test() {
SuffixAutomaton sa(s);
t.stop();
hash_t hash = 0;
- for (ll c = 0; c < sz(s);) {
+ for (ll c = 0; c < ssize(s);) {
int m = Random::integer<int>(1, 1000);
s = Random::string(m, "abc");
t.start();
diff --git a/test/string/suffixTree.cpp b/test/string/suffixTree.cpp
index 9181c2e..6f3d912 100644
--- a/test/string/suffixTree.cpp
+++ b/test/string/suffixTree.cpp
@@ -2,8 +2,8 @@
#include <string/suffixTree.cpp>
vector<string> naive(string_view s) {
- vector<string> res(sz(s));
- for (ll i = 0; i < sz(s); i++) {
+ vector<string> res(ssize(s));
+ for (ll i = 0; i < ssize(s); i++) {
res[i] = s.substr(i);
}
return res;
@@ -19,7 +19,7 @@ void stress_test() {
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;
+ if (pref.back() == '#') got[n + 1 - ssize(pref)] = pref;
for (auto [__, j] : next) {
self(self, pref, j);
}
@@ -39,7 +39,7 @@ void performance_test() {
t.start();
SuffixTree st(s);
t.stop();
- hash_t hash = sz(st.tree);
+ hash_t hash = ssize(st.tree);
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/string/z.cpp b/test/string/z.cpp
index f190482..a11984a 100644
--- a/test/string/z.cpp
+++ b/test/string/z.cpp
@@ -2,9 +2,9 @@
#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]++;
+ vector<int> res(ssize(s));
+ for (int i = 1; i < ssize(s); i++) {
+ while (i + res[i] < ssize(s) && s[res[i]] == s[i + res[i]]) res[i]++;
}
return res;
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:09:43 +0000