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。。