[HDU 4787]GRE Words Revenge

操作有兩種：
1. 學一個單字
2. 讀一篇文章，問你有幾個子字串是背過的單字 (只要位置或長度不同就是不同的子字串)

如果先學完所有單字，然後給要你讀幾篇文章問你答案，可以怎麼做呢？

首先對所有單字建立$AC$自動機，然後讓每篇文章在$AC$自動機裡面轉移
每走到一個點，就把答案加上「沿著失配邊可以走到的單字結尾數量」
可以對「將所有失配邊反向形成的樹」建立樹壓平序列

把樹壓平就是對樹做一次$dfs$，把每個點的進入和離開時間記錄下來即可
這樣任何一棵子樹都可以用一個區間表示了

用線段樹來維護這個樹壓平序列
每個單字結尾相當於把整個子樹都$+1$ (實作上將樹壓平序列對應的區間$+1$)，可以使用線段樹的區間修改
「沿著失配邊可以走到的單字結尾數量」相當於樹壓平序列上對應點的值，可以使用線段樹的單點查詢
這樣讓大小$N$的$AC$自動機讀入長度$L$的文章，時間複雜度為$O(L\log N)$

現在，需要動態新增字串 (單字)
可是$AC$自動機的失配邊只能離線建立
怎麼辦呢？

解決方案：
$BIT$ ($Binary\ Indexed\ Tree$) 套$AC$自動機

當新增第$N$個字串時，$BIT$的第$N$個元素就是第$N-lowbit(N)+1$個到第$N$個字串組成的$AC$自動機
讀文章時，$BIT$查詢$\log N$個自動機把答案加起來即可

加字串到$BIT$前需要先判斷這個單字有無背過，否則會重複計算

時間複雜度：$O(10^{5}\log 10^{5}+(5*10^{6})\log^{2}10^{5})$

code:

[POJ 3415]Common Substrings (題解二)

請先參考題解一

上一篇有提到我們讓$B$在$A$的後綴自動機裡面進行轉移時，每走一步就要往失配邊回溯直到$max\_len<K$為止
那我們能不能把這個過程加速呢？

我們可以套用$O(\log N)$尋找$LCA$ ($Lowest\ Common\ Ancestor$) 的思想
考慮使用倍增的方法，我們對於每個點預先算好往失配邊走$1$步、走$2$步、走$4$步、走$8$步......會答案加多少
然後就可以盡量跨大步，同時維持$max\_len>=K$
這樣最多跨$\log\left|A\right|$步，形同在$O(\log\left|A\right|)$的時間複雜度內走完失配邊！
注意，還需要做一些加加減減的小細節才是要求的答案

預處理可以做到$O(\left|A\right|\log\left|A\right|)$
我的作法是先將所有失配邊反向形成的樹建出來，然後用$dfs$的方式以類似$LCA$的預處理方式算出需要的資料

這樣就做完了嗎？
好像還沒耶

注意到這裡的字元集大小是$52$ (題目沒說會全部小寫)！
這樣最多會需要$2*10^{5}*52$的時間和空間來初始化並建立後綴自動機
對這題的時限來說實在太大了

因此必須使用更省時間空間的方案
我自己實作了$list$

時間複雜度：$O(\left|A\right|\log\left|A\right|+\left|B\right|\log\left|A\right|)$

code:

[POJ 3415]Common Substrings (題解一)

從這題，我們已經知道在枚舉$B$的前綴$B_{p}$時，如何求出$B_{p}$最長的後綴，使得這個後綴同時也是$A$的子字串
方法就是讓$B$在$A$的後綴自動機裡面轉移，同時維護目前答案的長度 (稱作$len$)

那要怎麼求出節點$u$代表的最長字串在$A$裡面出現幾個地方呢？
就是「代表$A$的前綴的節點集合」中，有幾個可以直接或間接透過失配邊走到$u$囉～

這些資訊可以利用$queue$先進行預處理，我們得到一個儲存答案的陣列$count$

於是在$B$進行轉移時，我們每走一步，就將目前找到的最長屬於$A$子字串的後綴$S$，沿著失配邊枚舉$S$的後綴集合，然後把它們在$A$中出現的次數全部加進答案裡面
實作上可以將沿著失配邊走的路徑上的每個節點的$count$乘上一個權重，再加起來
權重就是這個節點代表的字串集合中有幾個長度$\geq K$且$\leq \left|S\right|$，透過$len$和每個節點的$max\_len$資訊可以$O(1)$計算出來

這篇先講到這裡，並給出實現目前算法的code
下一篇說明怎麼讓時間複雜度再降低

時間複雜度：$O(\left|A\right|+\left|A\right|\left|B\right|)$

code:

[公告]code風景區瀏覽量破五千囉！

非常感謝大家的支持，讓code風景區自1/7開站以來瀏覽量首度破五千！
為了讓以後的文章更好，有任何改善建議請隨時留言或寄信給小莫，小莫會盡量在短時間內立即回覆並試用！

相信code風景區的進步，大家有目共睹

從引入latex語法 (感謝CBD)、字體調整、版面和文章結構、時間複雜度分析、圖片輔助說明 (感謝教室白板)、code中加入註解 (感謝程式設計社學長)、......

對code風景區來說都是一大躍進！

因為有你們，code風景區才能變得更好

請踴躍留言

請踴躍留言

請踴躍留言

因為很重要所以說三次

另外，小莫還發現一件事，不藏私地告訴大家：

將「code風景區」設為首頁，連結到各大OJ都方便！

真的是這樣啦不騙你XD

不然至少也加進我的最愛列嘛www (然後那些OJ的連結就可以全部刪掉了(?) )

對了

如果覺得「code風景區」同時有英文和中文，輸入不方便的話

現在Google搜尋「code scenic」也可以找到「code風景區」囉～

Email：fsps60312@yahoo.com.tw

以下為code風景區瀏覽量破五千時的網頁畫面：

[Codeforces 547E]Mike and Friends

如果要看懂這個題解，必須先了解「後綴陣列和其衍生的$height$陣列」的性質

這裡的詢問很特別，要你算出第$l$到第$r$隻熊會打給第$k$隻熊幾次
我們可以反向思考，怎麼求出第$k$隻熊會被哪幾隻熊打電話呢？

說明：
$phone[i]$為第$i$隻熊的電話代表的字串

可以考慮把所有熊的電話號碼接起來 (稱新字串為$S$)，中間用空字元隔開
如果我們對$S$建立它的後綴陣列和其衍生的$height$陣列
那麼對於第$k$隻熊，會打電話給它的就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間$_{(tag\ 1)}$了
利用後綴陣列來代出這個區間中的每個點分別對應到$S$的哪些位置，就能知道是哪幾隻熊打幾次電話給它了！

可是一個一個代出是哪隻熊打的電話，再篩選出第$l$到第$r$隻熊，實在太花時間了
我們可以考慮離線作法
可以發現，對於$height$陣列的一個區間$[l_{h},r_{h}]$，我們可以用「($height$中區間$[1,r_{h}]$有幾隻是第$l$到第$r$隻熊)$-$($height$中區間$[1,l_{h}-1]$有幾隻是第$l$到第$r$隻熊)」來算出$height$中區間$[l_{h},r_{h}]$有幾隻是第$l$到第$r$隻熊

因此，我們可以把所有的詢問分割成一個個形如「$height$中區間$[1,x]$有幾隻是第$l$到第$r$隻熊」的子問題，將這些子問題依照$x$排序，然後讓$i$由小到大跑，將$height[i]$在$S$上對應到的位置加進線段樹中維護
這樣對於每個子問題，$i$跑到$x$時，就可以直接利用線段樹的區間查詢，求出$[l,r]$有幾隻熊了

每個詢問的答案就是它對應到的兩個子問題答案相減

$Tags$：
$_{tag\ 1}$：將每隻熊的電話號碼由長到短排序，$height$由大到小排序，然後就可以在$x$遞減的情況下，利用$disjoint\ sets$維護$height$上高度$\geq x$的連通塊，當$x$等於第$k$熊的電話號碼長度時，就可以直接利用$disjoint\ sets$求出所在連通塊的左界和右界，也就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間

時間複雜度：$O((\sum_{i=1}^{N}\left|phone[i]\right|)\log(\sum_{i=1}^{N}\left|phone[i]\right|)+Q\log(\sum_{i=1}^{N}\left|phone[i]\right|))$

code:

[Codeforces 547E]Cyclical Quest

題目就是給你字串$S$，然後再給你一堆$A_{i}$，問你$S$有幾個子字串和$A_{i}$循環等價

可以考慮對$S$製作後綴自動機
然後對每個$i$ ($1\leq i\leq N$)
把$A_{i}$複製一遍接在後面 (稱新字串為$B$)
讓$B$在自動機裡面進行轉移
可以立即得到當前$B$的前綴屬於$S$的子字串的最長後綴 (請參考這裡)
如果後綴長度$\geq \left|A_{i}\right|$，就把這點標記起來，代表如果某個代表$S$前綴的點可以透過失配邊直接或間接指到這點，那麼這個點代表的$S$前綴的後綴就是符合條件的子字串
當然，因為要找出盡量多符合條件的$S$子字串，所以如果目前節點往失配邊走，代表的字串長度還是$\geq \left|A_{i}\right|$，就得往失配邊走

可以發現
後綴自動機的所有失配邊反向後會形成一棵根為$0$的樹
而答案就是這些被標記的點和其子節點們之中有幾個代表$S$的前綴

我們可以先把這棵樹壓平 ($dfs$並存下進入和離開時間即可)，讓每棵子樹都可以用一個區間來表示
然後用線段樹來維護，可以先預處理，用單點修改將所有代表$S$前綴的點加入
然後要求$u$和其子節點們之中有幾個代表$S$的前綴時，只要線段樹查詢子樹對應的區間的總和就好了

要注意被標記的點中有可能出現某個點是另外一個點的子節點的情況
為了避免重複計算
我們先把標記的點依照$dfs$後序排序 (設序列變成$\{v_{1},v_{2},v_{3},...\}$)，這樣如果$v_{a}$是$v_{b}$的子節點，那麼$v_{a+1},v_{a+2},...,v_{b-1}$也都會是$v_{b}$的子節點
用$stack$維護互不屬於父子關係的節點們即可

時間複雜度：$O(\left|S\right|+\sum_{i=1}^{N}\left|A_{i}\right|)$

code:

[Codeforces 163E]e-Government

這題給你一個字串集合$\{A_{i}\}$ ($1\leq i\leq N$)
然後是$Q$個操作，分為三種
1. 將$A_{i}$從集合中移除
2. 將$A_{i}$加回集合中
3. 給你字串$S$，問你$S$中可以數出幾個$\{A_{i}\}$的元素？
例如$\{A_{i}\}=\{"a","aa","aaa"\}$，$S="aaaa"$，你應該回答$9$

我們可以先把$\{A_{i}\}$建成$AC$自動機，然後讓$S$在裡面進行轉移
每走一個點，就將沿著失配邊可以走到的所有單字結尾的計數器都$+1$
走完時，每個單字結尾的計數器數值加起來就是答案了

當然，真的這麼做會TLE，每走一步就沿失配邊遍歷每個可以走到的單字結尾實在太花時間了

可以發現，將所有的失配邊反向可以形成一棵根節點為$0$的樹
於是我們就可以建立這棵樹的壓扁序列，這樣每棵子樹就都能剛好對應到一個區間了

那要怎麼做到快速的將沿著失配邊可以走到的所有單字結尾的計數器都$+1$呢？
反向思考，為甚麼我們不先把所有點的$+1$次數都算好？

於是，我們可以將每個以單字結尾為根的子樹全部$+1$
可以透過用線段樹維護樹壓扁序列，實現區間修改來達成

於是，要怎麼取得某個節點沿著失配邊走會遇到幾個單字結尾呢？
就是線段樹的單點查詢啦！

於是操作3.我們可以做到時間複雜度$O(\left|S\right|\log(\sum_{i=1}^{N}\left|A_{i}\right|))$！

那麼操作1.和2.呢？
移除單字相當於將以對應的單字結尾為根的子樹裡的每個點全部$-1$
那麼加回單字當然就是將子樹裡的每個點全部$+1$了
將樹壓扁序列對應的區間做適當的區間修改即可
時間複雜度$O(\log(\sum_{i=1}^{N}\left|A_{i}\right|))$

總時間複雜度：$O(\sum_{i=1}^{N}\left|A_{i}\right|+(\sum S)\log(\sum_{i=1}^{N}\left|A_{i}\right|)+Q\log(\sum_{i=1}^{N}\left|A_{i}\right|))$

code: