某岛

… : "…アッカリ~ン . .. . " .. .
August 8, 2014

Codeforces Round #129 (Div. 1) Problem E. Little Elephant and Strings

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  

。。对于任意一个 xlen。。。
。。我们需要在后缀数组中,找到最大的包含 x[l, r] 区间。。满足 lcp(l, r) ≥ len

。。而这又是一个二分过程。。。(。。这里需要用到 SA 的一个性质。。然后对于任一个串 Plcp(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。。