diff options
| -rw-r--r-- | string/string.tex | 1 | ||||
| -rw-r--r-- | string/suffixArray.cpp | 29 | ||||
| -rw-r--r-- | tcr.pdf | bin | 669912 -> 668072 bytes |
3 files changed, 15 insertions, 15 deletions
diff --git a/string/string.tex b/string/string.tex index 850c661..52284d9 100644 --- a/string/string.tex +++ b/string/string.tex @@ -90,7 +90,6 @@ \method{lcp}{berechnet den logest common prefix}{\log(\abs{s})} \method{}{von \code{s[x]} und \code{s[y]}}{} \end{methods} -\textbf{ACHTUNG:} \code{s} muss mit einem sentinel enden! \code{'\$'} oder \code{'#'} \sourcecode{string/suffixArray.cpp} \end{algorithm} diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp index 2423af7..c87e34f 100644 --- a/string/suffixArray.cpp +++ b/string/suffixArray.cpp @@ -1,31 +1,32 @@ struct SuffixArray { - int n, step, count; + int n, s, c; vector<int> SA, LCP; vector<vector<int>> P; - vector<pair<pair<int, int>, int>> L; + vector<ll> L; SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n), L(n) { P.assign(__lg(n)+2, vector<int>(n)); for (int i = 0; i < n; i++) P[0][i] = s[i]; - for (step = 1, count = 1; count < n; step++, count *= 2) { - for (int i = 0; i < n; i++) - L[i] = {{P[step-1][i], - i+count < n ? P[step-1][i+count] : -1}, i}; - sort(all(L)); - for (int i = 0; i < n; i++) { - P[step][L[i].second] = - i > 0 && L[i].first == L[i-1].first ? - P[step][L[i-1].second] : 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]; + sort(all(SA), [&](int a, int b){ + return L[a] != L[b] ? L[a] < L[b] : a < b; + }); + P[s][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]] + : i+1; }} - for (int i = 0; i < n; i++) SA[i] = L[i].second; - for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i - 1], SA[i]); + for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i-1], SA[i]); } // x and y are text-indices, not SA-indices. int lcp(int x, int y) { int ret = 0; if (x == y) return n - x; - for (int k = step - 1; k >= 0 && x < n && y < n; k--) { + 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; Binary files differ |