summaryrefslogtreecommitdiff
path: root/content/string
diff options
context:
space:
mode:
Diffstat (limited to 'content/string')
-rw-r--r--content/string/ahoCorasick.cpp11
-rw-r--r--content/string/deBruijn.cpp2
-rw-r--r--content/string/duval.cpp6
-rw-r--r--content/string/kmp.cpp8
-rw-r--r--content/string/longestCommonSubsequence.cpp8
-rw-r--r--content/string/lyndon.cpp2
-rw-r--r--content/string/manacher.cpp6
-rw-r--r--content/string/rollingHash.cpp2
-rw-r--r--content/string/rollingHashCf.cpp2
-rw-r--r--content/string/string.tex14
-rw-r--r--content/string/suffixArray.cpp19
-rw-r--r--content/string/suffixAutomaton.cpp12
-rw-r--r--content/string/suffixTree.cpp10
-rw-r--r--content/string/trie.cpp4
-rw-r--r--content/string/z.cpp2
15 files changed, 55 insertions, 53 deletions
diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp
index 390d16d..d738961 100644
--- a/content/string/ahoCorasick.cpp
+++ b/content/string/ahoCorasick.cpp
@@ -4,7 +4,8 @@ struct AhoCorasick {
int suffix = 0, ch, cnt = 0;
array<int, ALPHABET_SIZE> nxt = {};
- vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);}
+ vert(int p, int c):
+ suffix(-p), ch(c) { ranges::fill(nxt, -1); }
};
vector<vert> aho = {{0, -1}};
@@ -13,7 +14,7 @@ struct AhoCorasick {
for (auto c : s) {
int idx = c - OFFSET;
if (aho[v].nxt[idx] == -1) {
- aho[v].nxt[idx] = sz(aho);
+ aho[v].nxt[idx] = ssize(aho);
aho.emplace_back(v, idx);
}
v = aho[v].nxt[idx];
@@ -37,9 +38,9 @@ struct AhoCorasick {
vector<vector<int>> adj;
vector<ll> dp;
void buildGraph() {
- adj.resize(sz(aho));
- dp.assign(sz(aho), 0);
- for (int i = 1; i < sz(aho); i++) {
+ adj.resize(ssize(aho));
+ dp.assign(ssize(aho), 0);
+ for (int i = 1; i < ssize(aho); i++) {
adj[getSuffix(i)].push_back(i);
}}
diff --git a/content/string/deBruijn.cpp b/content/string/deBruijn.cpp
index e829137..545dde7 100644
--- a/content/string/deBruijn.cpp
+++ b/content/string/deBruijn.cpp
@@ -1,7 +1,7 @@
string deBruijn(int n, char mi = '0', char ma = '1') {
string res, c(1, mi);
do {
- if (n % sz(c) == 0) res += c;
+ if (n % ssize(c) == 0) res += c;
} while(next(c, n, mi, ma));
return res;
}
diff --git a/content/string/duval.cpp b/content/string/duval.cpp
index 253bae1..de94ebd 100644
--- a/content/string/duval.cpp
+++ b/content/string/duval.cpp
@@ -1,8 +1,8 @@
vector<pair<int, int>> duval(const string& s) {
vector<pair<int, int>> res;
- for (int i = 0; i < sz(s);) {
+ for (int i = 0; i < ssize(s);) {
int j = i + 1, k = i;
- for (; j < sz(s) && s[k] <= s[j]; j++) {
+ for (; j < ssize(s) && s[k] <= s[j]; j++) {
if (s[k] < s[j]) k = i;
else k++;
}
@@ -15,5 +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 (r >= sz(s)) return l;
+ if (r >= ssize(s)) return l;
}}
diff --git a/content/string/kmp.cpp b/content/string/kmp.cpp
index 421479e..a354aa7 100644
--- a/content/string/kmp.cpp
+++ b/content/string/kmp.cpp
@@ -1,7 +1,7 @@
vector<int> kmpPreprocessing(const string& sub) {
- vector<int> b(sz(sub) + 1);
+ vector<int> b(ssize(sub) + 1);
b[0] = -1;
- for (int i = 0, j = -1; i < sz(sub);) {
+ for (int i = 0, j = -1; i < ssize(sub);) {
while (j >= 0 && sub[i] != sub[j]) j = b[j];
b[++i] = ++j;
}
@@ -9,10 +9,10 @@ vector<int> kmpPreprocessing(const string& sub) {
}
vector<int> kmpSearch(const string& s, const string& sub) {
vector<int> result, pre = kmpPreprocessing(sub);
- for (int i = 0, j = 0; i < sz(s);) {
+ for (int i = 0, j = 0; i < ssize(s);) {
while (j >= 0 && s[i] != sub[j]) j = pre[j];
i++; j++;
- if (j == sz(sub)) {
+ if (j == ssize(sub)) {
result.push_back(i - j);
j = pre[j];
}}
diff --git a/content/string/longestCommonSubsequence.cpp b/content/string/longestCommonSubsequence.cpp
index 6c9ea44..14ca62c 100644
--- a/content/string/longestCommonSubsequence.cpp
+++ b/content/string/longestCommonSubsequence.cpp
@@ -1,12 +1,12 @@
string lcss(const string& a, const string& b) {
- vector<vector<int>> m(sz(a) + 1, vector<int>(sz(b) + 1));
- for (int i = sz(a) - 1; i >= 0; i--) {
- for (int j = sz(b) - 1; j >= 0; j--) {
+ vector<vector<int>> m(ssize(a) + 1, vector<int>(ssize(b) + 1));
+ for (int i = ssize(a) - 1; i >= 0; i--) {
+ for (int j = ssize(b) - 1; j >= 0; j--) {
if (a[i] == b[j]) m[i][j] = 1 + m[i+1][j+1];
else m[i][j] = max(m[i+1][j], m[i][j+1]);
}} // Für die Länge: return m[0][0];
string res;
- for (int j = 0, i = 0; j < sz(b) && i < sz(a);) {
+ for (int j = 0, i = 0; j < ssize(b) && i < ssize(a);) {
if (a[i] == b[j]) res += a[i++], j++;
else if (m[i][j+1] > m[i+1][j]) j++;
else i++;
diff --git a/content/string/lyndon.cpp b/content/string/lyndon.cpp
index e44379b..cb477d4 100644
--- a/content/string/lyndon.cpp
+++ b/content/string/lyndon.cpp
@@ -1,5 +1,5 @@
bool next(string& s, int maxLen, char mi = '0', char ma = '1') {
- for (int i = sz(s), j = sz(s); i < maxLen; i++)
+ for (int i = ssize(s), j = ssize(s); i < maxLen; i++)
s.push_back(s[i % j]);
while(!s.empty() && s.back() == ma) s.pop_back();
if (s.empty()) {
diff --git a/content/string/manacher.cpp b/content/string/manacher.cpp
index 112bd55..9fa2991 100644
--- a/content/string/manacher.cpp
+++ b/content/string/manacher.cpp
@@ -1,9 +1,9 @@
vector<int> manacher(const string& t) {
//transforms "aa" to ".a.a." to find even length palindromes
- string s(sz(t) * 2 + 1, '.');
- for (int i = 0; i < sz(t); i++) s[2 * i + 1] = t[i];
+ string s(ssize(t) * 2 + 1, '.');
+ for (int i = 0; i < ssize(t); i++) s[2 * i + 1] = t[i];
- int mid = 0, r = 0, n = sz(s);
+ int mid = 0, r = 0, n = ssize(s);
vector<int> pal(n);
for (int i = 1; i < n - 1; i++) {
if (r > i) pal[i] = min(r - i, pal[2 * mid - i]);
diff --git a/content/string/rollingHash.cpp b/content/string/rollingHash.cpp
index 6e914aa..1157cb7 100644
--- a/content/string/rollingHash.cpp
+++ b/content/string/rollingHash.cpp
@@ -14,5 +14,5 @@ struct Hash {
return (pref[r] - mul(power[r-l], pref[l]) + M) % M;
}
- static ll mul(__int128 a, ll b) {return a * b % M;}
+ static ll mul(__int128 a, ll b) { return a * b % M; }
};
diff --git a/content/string/rollingHashCf.cpp b/content/string/rollingHashCf.cpp
index 84b2e4e..c08a9d3 100644
--- a/content/string/rollingHashCf.cpp
+++ b/content/string/rollingHashCf.cpp
@@ -13,5 +13,5 @@ struct Hash {
return (pref[r] - mul(power[r-l], pref[l]) + M) % M;
}
- static ll mul(__int128 a, ll b) {return a * b % M;}
+ static ll mul(__int128 a, ll b) { return a * b % M; }
};
diff --git a/content/string/string.tex b/content/string/string.tex
index bedabfb..0e482bf 100644
--- a/content/string/string.tex
+++ b/content/string/string.tex
@@ -63,21 +63,21 @@
\end{algorithm}
\clearpage
-\begin{algorithm}{Lyndon und De-Bruijn}
+\begin{algorithm}{\textsc{Lyndon} und \textsc{De-Bruijn}}
\begin{itemize}
- \item \textbf{Lyndon-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen.
- \item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von Lyndon-Worten zerlegt werden.
- \item Für Lyndon-Worte $u, v$ mit $u<v$ gilt, dass $uv$ auch ein Lyndon-Wort ist.
+ \item \textbf{\textsc{Lyndon}-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen.
+ \item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von \textsc{Lyndon}-Worten zerlegt werden.
+ \item Für \textsc{Lyndon}-Worte $u, v$ mit $u<v$ gilt, dass $uv$ auch ein \textsc{Lyndon}-Wort ist.
\end{itemize}
\begin{methods}
- \method[, Durchschnitt $\Theta(1)$]{next}{lexikographisch nächstes Lyndon-Wort}{n}
- \method{duval}{zerlegt $s$ in Lyndon-Worte}{n}
+ \method[, Durchschnitt $\Theta(1)$]{next}{lexikographisch nächstes \textsc{Lyndon}-Wort}{n}
+ \method{duval}{zerlegt $s$ in \textsc{Lyndon}-Worte}{n}
\method{minrotation}{berechnet kleinste Rotation von $s$}{n}
\end{methods}
\sourcecode{string/lyndon.cpp}
\sourcecode{string/duval.cpp}
\begin{itemize}
- \item \textbf{De-Bruijn-Sequenze $\boldsymbol{B(\Sigma, n)}$:}~~~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird.
+ \item \textbf{\textsc{De-Bruijn}-Sequenz $\boldsymbol{B(\Sigma, n)}$:}~~~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird.
\item es gibt $\frac{(k!)^{k^{n-1}}}{k^{n}}$ verschiedene $B(\Sigma, n)$
\item $B(\Sigma, n)$ hat Länge $\abs{\Sigma}^n$
\end{itemize}
diff --git a/content/string/suffixArray.cpp b/content/string/suffixArray.cpp
index 8b698d2..65bbb38 100644
--- a/content/string/suffixArray.cpp
+++ b/content/string/suffixArray.cpp
@@ -4,22 +4,22 @@ struct SuffixArray {
vector<int> SA, LCP;
vector<vector<int>> P;
- SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n),
+ SuffixArray(const string& s) : n(ssize(s)), SA(n), LCP(n),
P(__lg(2 * n - 1) + 1, vector<int>(n)) {
- P[0].assign(all(s));
- iota(all(SA), 0);
- sort(all(SA), [&](int a, int b) {return s[a] < s[b];});
+ P[0].assign(begin(s), end(s));
+ iota(begin(SA), end(SA), 0);
+ ranges::sort(SA, {}, [&](int x) { return s[x]; });
vector<int> x(n);
for (int k = 1, c = 1; c < n; k++, c *= 2) {
- iota(all(x), n - c);
+ iota(begin(x), end(x), n - c);
for (int ptr = c; int i : SA) if (i >= c) x[ptr++] = i - c;
vector<int> cnt(k == 1 ? MAX_CHAR : n);
for (int i : P[k-1]) cnt[i]++;
- partial_sum(all(cnt), begin(cnt));
+ partial_sum(begin(cnt), end(cnt), begin(cnt));
for (int i : x | views::reverse) SA[--cnt[P[k-1][i]]] = i;
- auto p = [&](int i) {return i < n ? P[k-1][i] : -1;};
+ auto p = [&](int i) { return i < n ? P[k-1][i] : -1; };
for (int i = 1; i < n; i++) {
int a = SA[i-1], b = SA[i];
P[k][b] = P[k][a] + (p(a) != p(b) || p(a+c) != p(b+c));
@@ -27,10 +27,11 @@ struct SuffixArray {
for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i-1], SA[i]);
}
- int lcp(int x, int y) {//x & y are text-indices, not SA-indices
+ // x & y are text-indices, not SA-indices
+ int lcp(int x, int y) {
if (x == y) return n - x;
int res = 0;
- for (int i = sz(P) - 1; i >= 0 && max(x, y) + res < n; i--) {
+ for (int i = ssize(P)-1; i >= 0 && max(x, y) + res < n; i--){
if (P[i][x + res] == P[i][y + res]) res |= 1 << i;
}
return res;
diff --git a/content/string/suffixAutomaton.cpp b/content/string/suffixAutomaton.cpp
index 9a68cb3..f9aa80b 100644
--- a/content/string/suffixAutomaton.cpp
+++ b/content/string/suffixAutomaton.cpp
@@ -4,20 +4,20 @@ struct SuffixAutomaton {
struct State {
int len, link = -1;
array<int, ALPHABET_SIZE> nxt; // map if large Alphabet
- State(int l) : len(l) {fill(all(nxt), -1);}
+ State(int l): len(l) { ranges::fill(nxt, -1); }
};
vector<State> st = {State(0)};
int cur = 0;
SuffixAutomaton(const string& s) {
- st.reserve(2 * sz(s));
+ st.reserve(2 * ssize(s));
for (auto c : s) extend(c - OFFSET);
}
void extend(int c) {
int p = cur;
- cur = sz(st);
+ cur = ssize(st);
st.emplace_back(st[p].len + 1);
for (; p != -1 && st[p].nxt[c] < 0; p = st[p].link) {
st[p].nxt[c] = cur;
@@ -33,9 +33,9 @@ struct SuffixAutomaton {
st.back().link = st[q].link;
st.back().nxt = st[q].nxt;
for (; p != -1 && st[p].nxt[c] == q; p = st[p].link) {
- st[p].nxt[c] = sz(st) - 1;
+ st[p].nxt[c] = ssize(st) - 1;
}
- st[q].link = st[cur].link = sz(st) - 1;
+ st[q].link = st[cur].link = ssize(st) - 1;
}}}
vector<int> calculateTerminals() {
@@ -49,7 +49,7 @@ struct SuffixAutomaton {
// Pair with start index (in t) and length of LCS.
pair<int, int> longestCommonSubstring(const string& t) {
int v = 0, l = 0, best = 0, bestp = -1;
- for (int i = 0; i < sz(t); i++) {
+ for (int i = 0; i < ssize(t); i++) {
int c = t[i] - OFFSET;
while (v > 0 && st[v].nxt[c] < 0) {
v = st[v].link;
diff --git a/content/string/suffixTree.cpp b/content/string/suffixTree.cpp
index 7112f39..6362c3e 100644
--- a/content/string/suffixTree.cpp
+++ b/content/string/suffixTree.cpp
@@ -11,12 +11,12 @@ struct SuffixTree {
SuffixTree(const string& s_) : s(s_) {
needsSuffix = remainder = curVert = curEdge = curLen = 0;
pos = -1;
- for (int i = 0; i < sz(s); i++) extend();
+ for (int i = 0; i < ssize(s); i++) extend();
}
int newVert(int start, int end) {
tree.push_back({start, end, 0, {}});
- return sz(tree) - 1;
+ return ssize(tree) - 1;
}
void addSuffixLink(int vert) {
@@ -42,7 +42,7 @@ struct SuffixTree {
while (remainder) {
if (curLen == 0) curEdge = pos;
if (!tree[curVert].nxt.count(s[curEdge])) {
- int leaf = newVert(pos, sz(s));
+ int leaf = newVert(pos, ssize(s));
tree[curVert].nxt[s[curEdge]] = leaf;
addSuffixLink(curVert);
} else {
@@ -56,7 +56,7 @@ struct SuffixTree {
int split = newVert(tree[nxt].start,
tree[nxt].start + curLen);
tree[curVert].nxt[s[curEdge]] = split;
- int leaf = newVert(pos, sz(s));
+ int leaf = newVert(pos, ssize(s));
tree[split].nxt[s[pos]] = leaf;
tree[nxt].start += curLen;
tree[split].nxt[s[tree[nxt].start]] = nxt;
@@ -69,4 +69,4 @@ struct SuffixTree {
} else {
curVert = tree[curVert].suf ? tree[curVert].suf : 0;
}}}
-}; \ No newline at end of file
+};
diff --git a/content/string/trie.cpp b/content/string/trie.cpp
index 03cf947..db39c43 100644
--- a/content/string/trie.cpp
+++ b/content/string/trie.cpp
@@ -3,7 +3,7 @@ constexpr int ALPHABET_SIZE = 2;
struct node {
int words, ends;
array<int, ALPHABET_SIZE> nxt;
- node() : words(0), ends(0) {fill(all(nxt), -1);}
+ node(): words(0), ends(0) { ranges::fill(nxt, -1); }
};
vector<node> trie = {node()};
@@ -13,7 +13,7 @@ int traverse(const vector<int>& word, int x) {
if (id < 0 || (trie[id].words == 0 && x <= 0)) return -1;
trie[id].words += x;
if (trie[id].nxt[c] < 0 && x > 0) {
- trie[id].nxt[c] = sz(trie);
+ trie[id].nxt[c] = ssize(trie);
trie.emplace_back();
}
id = trie[id].nxt[c];
diff --git a/content/string/z.cpp b/content/string/z.cpp
index 069fa38..0d8cafb 100644
--- a/content/string/z.cpp
+++ b/content/string/z.cpp
@@ -1,5 +1,5 @@
vector<int> Z(const string& s) {
- int n = sz(s);
+ int n = ssize(s);
vector<int> z(n);
for (int i = 1, x = 0; i < n; i++) {
z[i] = max(0, min(z[i - x], x + z[x] - i));
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:26:40 +0000