diff options
| author | Gloria Mundi <gloria@gloria-mundi.eu> | 2024-11-16 17:48:10 +0100 |
|---|---|---|
| committer | Gloria Mundi <gloria@gloria-mundi.eu> | 2024-11-16 18:01:53 +0100 |
| commit | e55df069a8f83b2c0c2b56c035f49e89516cdaaa (patch) | |
| tree | dd6767e3fc6ac8532661dc75886a3056804d1d46 /content/string/suffixArray.cpp | |
| parent | 72bd993483453ed8ebc462f1a33385cd355d486f (diff) | |
minor fixes, let code breathe where possible
Diffstat (limited to 'content/string/suffixArray.cpp')
| -rw-r--r-- | content/string/suffixArray.cpp | 7 |
1 files changed, 4 insertions, 3 deletions
diff --git a/content/string/suffixArray.cpp b/content/string/suffixArray.cpp index 8b698d2..0e301b2 100644 --- a/content/string/suffixArray.cpp +++ b/content/string/suffixArray.cpp @@ -8,7 +8,7 @@ struct SuffixArray { 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];}); + sort(all(SA), [&](int a, int b) { return s[a] < s[b]; }); vector<int> x(n); for (int k = 1, c = 1; c < n; k++, c *= 2) { iota(all(x), n - c); @@ -19,7 +19,7 @@ struct SuffixArray { partial_sum(all(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,7 +27,8 @@ 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--) { |
