diff options
| -rw-r--r-- | string/suffixArray.cpp | 26 |
1 files changed, 13 insertions, 13 deletions
diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp index c87e34f..d584ebf 100644 --- a/string/suffixArray.cpp +++ b/string/suffixArray.cpp @@ -1,22 +1,22 @@ struct SuffixArray { - int n, s, c; + int n, k, c; vector<int> SA, LCP; vector<vector<int>> P; - vector<ll> L; - SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n), L(n) { + SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n) { + vector<ll> L(n); P.assign(__lg(n)+2, vector<int>(n)); for (int i = 0; i < n; i++) P[0][i] = s[i]; iota(all(SA), 0); - for (s = 1, c = 1; c < n; s++, c *= 2) { - for (int i = 0; i < n; i++) L[i] = (ll)P[s-1][i] << 32; - for (int i = 0; i+c < n; i++) L[i] |= P[s-1][i+c]; + for (k = 1, c = 1; c < n; k++, c *= 2) { + for (int i = 0; i < n; i++) L[i] = (ll)P[k-1][i] << 32; + for (int i = 0; i+c < n; i++) L[i] |= P[k-1][i+c]; sort(all(SA), [&](int a, int b){ return L[a] != L[b] ? L[a] < L[b] : a < b; }); - P[s][SA[0]] = 1; + P[k][SA[0]] = 1; for (int i = 1; i < n; i++) { - P[s][SA[i]] = L[SA[i]] == L[SA[i-1]] ? P[s][SA[i-1]] + P[k][SA[i]] = L[SA[i]] == L[SA[i-1]] ? P[k][SA[i-1]] : i+1; }} for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i-1], SA[i]); @@ -26,11 +26,11 @@ struct SuffixArray { int lcp(int x, int y) { int ret = 0; if (x == y) return n - x; - for (int k = s - 1; k >= 0 && x < n && y < n; k--) { - if (P[k][x] == P[k][y]) { - x += 1 << k; - y += 1 << k; - ret += 1 << k; + for (int i = k - 1; i >= 0 && x < n && y < n; i--) { + if (P[i][x] == P[i][y]) { + x += 1 << i; + y += 1 << i; + ret += 1 << i; }} return ret; } |