題目鏈接：BZOJ - 3238

?

題目分析

顯然，這道題就是求任意兩個(gè)后綴之間的LCP的和，這與后綴數(shù)組的聯(lián)系十分明顯。

求出后綴數(shù)組后，求出字典序相鄰兩個(gè)后綴的LCP，即 Height 數(shù)組。

那么我們可以用這個(gè) Height 數(shù)組求出所有后綴之間 LCP 的和。

我們用 f[i] 表示字典序第 i 的后綴與字典序在 i 之后的所有后綴的 LCP 的和。

我們知道，兩個(gè)后綴的 LCP 為 Height 數(shù)組中這兩個(gè)后綴之間的最小值。

我們從最后向前推 i ，用一個(gè)單調(diào)棧維護(hù)后面的 Height 單調(diào)不上升，然后用 St[Top] 來(lái)推 f[i] 即可，具體見(jiàn)代碼。

?

代碼

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm>using namespace std;const int MaxL = 500000 + 5;typedef long long LL;LL Ans, Temp; LL f[MaxL];int n, Top; int A[MaxL], Rank[MaxL], SA[MaxL], Height[MaxL], St[MaxL]; int VA[MaxL], VB[MaxL], VC[MaxL], Sum[MaxL];char S[MaxL];inline bool Cmp(int *a, int x, int y, int l) {return (a[x] == a[y]) && (a[x + l] == a[y + l]); }void DA(int *A, int n, int m) {int *x, *y, *t;x = VA; y = VB;for (int i = 1; i <= m; ++i) Sum[i] = 0;for (int i = 1; i <= n; ++i) ++Sum[x[i] = A[i]];for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1];for (int i = n; i >= 1; --i) SA[Sum[x[i]]--] = i;int p, q;p = 0;for (int j = 1; p < n; j <<= 1, m = p) { q = 0;for (int i = n - j + 1; i <= n; ++i) y[++q] = i;for (int i = 1; i <= n; ++i) {if (SA[i] <= j) continue;y[++q] = SA[i] - j;}for (int i = 1; i <= m; ++i) Sum[i] = 0;for (int i = 1; i <= n; ++i) VC[i] = x[y[i]];for (int i = 1; i <= n; ++i) ++Sum[VC[i]];for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1];for (int i = n; i >= 1; --i) SA[Sum[VC[i]]--] = y[i];t = x; x = y; y = t; p = 1;x[SA[1]] = 1;for (int i = 2; i <= n; ++i) x[SA[i]] = Cmp(y, SA[i], SA[i - 1], j) ? p : ++p;}for (int i = 1; i <= n; ++i) Rank[SA[i]] = i;//GetHeightint h = 0, o;for (int i = 1; i <= n; ++i) {if (Rank[i] == 1) continue;o = SA[Rank[i] - 1];while (A[i + h] == A[o + h]) ++h;Height[Rank[i]] = h;if (h > 0) --h;} }int main() {scanf("%s", S + 1);n = strlen(S + 1);for (int i = 1; i <= n; ++i) A[i] = S[i] - 'a' + 1;DA(A, n, 26);Ans = 0ll; Temp = 0ll;for (int i = 1; i <= n; ++i) Ans += (LL)(n - i + 1) * (LL)(n - 1);Top = 0;St[++Top] = n + 1;for (int i = n; i >= 2; --i) {while (Top > 0 && Height[St[Top]] > Height[i]) --Top;int x = St[Top];f[i] = (LL)Height[i] + (LL)Height[i] * (x - i - 1) + (LL)f[x];Temp += f[i];St[++Top] = i;}Ans -= Temp * 2ll;printf("%lld\n", Ans);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/JoeFan/p/4214575.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 3238] [AHOI 2013] 差异 【后缀数组 + 单调栈】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。