http://codeforces.com/problemset/problem/204/E
Brief description:
给定 n 个串。。问对于每一个字符串，有多少它的子串，可以至少匹配 k 个字符串。（包含自身）
Analysis:
后缀数组
算法1. 二分 + 可持久化线段树
首先当然还是要把所有串拼一起跑后缀数组。。。以aaa$aba$aaa 为例
考察第一个串。。记作 s0 = aaa 。。。我们枚举起始位 x。。
。。设 f(x, len)。。表示 。。。s0[x, x+len] 这个子串。。是否出现在了 k 个子串中。
。。。（。我们希望求最大的 len。。。。显然 len 越长对这个性质越不利。。
。。。（考虑二分。。。
$aaa $aba$aaa a a$aaa a$aba$aaa aa aa$aba$aaa aaa aaa$aba$aaa aba$aaa ba$aaa
。。对于任意一个 x 和 len。。。
。。我们需要在后缀数组中，找到最大的包含 x 的 [l, r] 区间。。满足 lcp(l, r) ≥ len。
。。而这又是一个二分过程。。。（。。这里需要用到 SA 的一个性质。。然后对于任一个串 P，lcp(P, SA[i]) 是单峰的。
。。找到 [l, r] 区间后。。。就是。。。。
。。。判断这个区间的后缀出现在了几个不同的字符串中。。。
。。。而这个是个可持久化线段树的入门题。。（参见 SPOJ Dquery 。。
。。。这样这个题我们就得到了最傻逼的做法。。。复杂度 $O(nlog^2n)$。
http://codeforces.com/contest/204/submission/4545205
算法 2. two-point
http://www.cppblog.com/hanfei19910905/archive/2012/07/26/185139.html
。。。上面的做法中。可持久化线段树。未免有点 overkill。。注意毕竟只是询问是否 >= k。。。
。而这个可以通过 two-point 离线搞出对于每个左端点。最早的合法位置。。。
具体做法是 prd[], suc[] 分别表示左右第一个与 b[i] 相同的位置。。
int last[N], prd[N], suc[N];
两遍循环。。
FOR_1(i, nn, n) prd[i] = last[bb(i)], last[bb(i)] = i;
REP_1(i, nn) last[i] = n + 1;
DWN_1(i, n, nn) suc[i] = last[bb(i)], last[bb(i)] = i;
之后 two-point。。
（l 增大的时候。。如果 suc[l] > r 。。c -= 1
（r 增大的时候。。如果 prd[++r] < l。。则 c += 1
[cpp]
for(int l=nn,r=nn-1,c;l<=n;c-=(suc[l++]>r)){
if (r<l) r=l,c=1; while(c<k&&r<=n) if(prd[++r]<l)++c; if (c<k){n=l-1;break;}
last[l] = r;
}
[/cpp]
其他地方不变。。。。。复杂度依旧是 O(nlog^2n)
http://codeforces.com/contest/204/submission/4544775
算法 3. 标记
。。为了杜绝掉二分的过程。。。我们注意到上面 two-point 得到一组最小的合法 (l, r, lcp) 的时候。。。
。。可以沿途打上事件标记。。。用扫描线的方法。弄一个平衡树。。每次取出最大的 lcp 好像就行了。。
http://hi.baidu.com/wyl8899/item/04772d462eeb6797823ae16d
..似乎已经做完了么...其实被坑了，样例2就可以把这个做法撸死。
究其原因，是存在某个k，他的真正可用的最大值并不能被上面所述的方法更新到。
这就坑爹了..因为能更新到k的最大值的那个区间，假设是[x,y']，会出现y'>y(使得rank为x..y的后缀分属K个串的最小y值)的情形。
。。然而这点也正是这题最精彩的地方。。。因为对于一组标记 (l, r, lcp) 来说。。
。。。r 之后并不代表这个标记就完全失效了。。而是以这个时刻开始。。。
。。随着时间的流逝。。产生衰减。。（说的神乎其神的。。具体来说就是每次 checkMin(delay, height[i])。。
因此。。我们每次除了要取出平衡树中的最大值以外。。还需要那些过了 “保质期” 的标记中的最大值。。
。。。然后从这两者之间。取最大值。。。。
。。 平衡树内的标记。。涉及增删操作。。最好的方法使用 multiset
。。 平衡树以外的标记。。只需保留一个最大值即可（记作 delay）。。然后随着时间的推移。每次 checkMin(delay, height[i])。。
http://codeforces.com/contest/204/submission/4544928
。。除去不多的几次平衡树操作。。这个算法的复杂度已经很接近 O(n) 了。。而且非常好写。。
。。。。是一个优秀的算法。
算法 4. 后缀自动机
https://www.13331.org/205.html
http://codeforces.com/contest/204/submission/2579006
——————
普通并查集。。。
http://codeforces.com/contest/204/submission/4601790 （280ms。。
加按秩合并。。
http://codeforces.com/contest/204/submission/4601803 （248ms。。
