(mathcal{A})
后缀数组
求法一般有(O(nlogn))的倍增，(O(n))的SA-IS，还有一个(O(nlog^2n))的hash。其中hash可以动态用set维护。
(ht[i])表示排名为(i)的后缀和排名为(i-1)的后缀的最长公共前缀长度。
单个字符串的相关问题的一个常用做法是先求后缀数组和 height数组，然后利用 height数组进行求解。
利用 height值对后缀进行分组的方法很常用，请读者认真体会。
给定一个字符串(s)
-
求本质不同的子串个数。
对于(sa[i])，假设排名前(i-1)个有(t)个本质不同的字串，以(sa[i])开始的共有(n - sa[i] + 1)个，但其中有(ht[i])个和(sa[i - 1])重复，所有排名前(i)个共有(t+n-sa[i]+1-ht[i])个，归纳得有(frac{n(n+1)}{2}-sum ht[i])。
-
求最长的两个相同子串，要求不相交。
二分答案。把(ht[i]geq mid)的分成一组。就是把(ht)数组划分成若干段。每段间(ht[i]geq mid)。
发现只有同一组之内的任意两个字串都满足(geq k)的要求，而不同之见的肯定不满足。
如果要不重复，只需(sa[i]-sa[j]>=k)。时间复杂度(O(nlogn))。
-
求(s)所有循环同构的字符串的顺序。([JSOI2007]字符加密)
从循环同构可以想到令(s'=ss)求(s')的(sa)数组。所有开始位置(leq n)的即为所有循环同构的字符串。
-
求每个(s[1..i])的本质不同的子串个数。([SDOI2016]生成魔咒)
相当于每次增加一个字符，动态维护(sa)数组。可以用前面的hash算法，用set维护。问题在于如何实时维护(ht)数组。假设(sa[k-1]<sa[k])，注意到只有(ht[k]=len-sa[k-1]+1)并且下个读入的字符和(s[sa[k] + len - sa[k-1]+1])相等时(ht[k])需要(+1),((len)表示当前读入的字符串的长度)这是没法优化的，每次修改，则总复杂度为(O(n^2))。考虑把字符串倒置，每次往前面加字符。这样(ht)数组不会改变，而答案显然也正确。
代码中的(ht)数组定义和先前的不同。(ht[i])表示(i)开始的后缀和(sa[rank[i]-1])开始的后缀的最长公共前缀长度。
#include <bits/stdc++.h> using namespace std; namespace cxcyl { const int mod = 1e9 + 7; int n, mi[100005], a[200005], hash[200005], ht[200005]; long long sum; inline int read() { int x = 0, f = 1; char c = getchar(); while (c > -1 && c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } if (c == -1) return 0; while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } inline int equal(int x, int y) { int l = 0, r = min(n - x + 1, n - y + 1), len = r; if (x > y) swap(x, y); while (l < r) { int mid = l + 1 + r >> 1; if ((1ll * mi[y - x] * (hash[x] - hash[x + mid]) % mod + mod) % mod == (hash[y] - hash[y + mid] + mod) % mod) l = mid; else r = mid - 1; } return l; } struct _cmp { inline bool operator()(int x, int y) { int t = equal(x, y); return a[x + t] < a[y + t]; } }; set<int, _cmp> s; inline int main() { n = read(); mi[0] = 1; for (int i = 1; i <= n; ++i) mi[i] = 7ll * mi[i - 1] % mod; for (int i = n; i >= 1; --i) { a[i] = read(); hash[i] = (hash[i + 1] + 1ll * mi[i] * a[i]) % mod; if (i < n) { auto x = s.upper_bound(i); if (x == s.end()) { ht[i] = equal(i, *(--x)); sum += ht[i]; } else if (x == s.begin()) { ht[*x] = equal(*x, i); sum += ht[*x]; } else { int v = *x, u = *(--x); ht[i] = equal(u, i); sum += ht[i]; sum -= ht[v]; ht[v] = equal(i, v); sum += ht[v]; } } s.insert(i); printf("%lld ", (n - i + 2ll) * (n - i + 1) / 2 - sum); } return 0; } } int main() { return cxcyl::main(); }
(mathcal{B})
关于整型溢出的问题。加入-ftrapv参数，在有溢出时会程序会崩溃。(Windows中把Dev-c++开成32位的才可用)
别用deque！据说空间会出乎意料的大。