字符串少量習(xí)題小結(jié).
spoj694(易) 后綴數(shù)組
求一個字串的不同子串個數(shù).
按rank考慮子串.加入子串S[i]時,獲得了len-Sa[i]個不同子串.但其中height[i]個已經(jīng)屬于S[i-1]了,所以實際子串?dāng)?shù)增加了len-Sa[i]-S[i-1]. 順序掃一遍height數(shù)組即得解.
spoj687(中) 后綴數(shù)組
求一個串的重復(fù)次數(shù)最多的連續(xù)重復(fù)子串.
設(shè)周期為L的連續(xù)重復(fù)子串存在,則點0,L,2L,...,kL必能覆蓋到一個完整周期. 因此對L,考察這些點的字符相等情況,LCP情況,可得到L的解.
枚舉L.
復(fù)雜度是O(n/1+n/2+...+n/n) = O(nlogn)
pku3693(中) 后綴數(shù)組
同spoj687,只是結(jié)果還要輸出字典序最小的滿足條件的串.可以借助rank數(shù)組直接比較字典序.只是要注意在考察點kL時,要把以(k-1)L+1,...,(k+1)L-1為起點的子串都訪問一遍找最小rank者.
pku1743(中) 后綴數(shù)組
找一個串的最長不重疊相同子串.
由于某子串可能整體加上(或減去)相同偏移量,因此不直接對原串操作,而是構(gòu)造新串b, 其中b[i]=a[i]-a[i-1]. 此時求得最長不重疊相同子串的長度+1便是結(jié)果.
可以二分長度,或者棧掃描(*)直接求最大長度.
whu1084(易) 后綴數(shù)組
求重復(fù)次數(shù)最多的不重疊子串長度
spoj687的簡單版,不要求循環(huán)節(jié)連續(xù),直接二分長度即可.
pku2778(易) 多串匹配+DP AC自動機,trie圖
字符集大小為4, 給出m個(m<=10)禁止單詞(長度<=10), 求長度為n(n<=2*10^9)的不包含任何禁止單詞的串的個數(shù).
對禁止單詞建立trie圖,并計算出圖中任意合法結(jié)點之間的轉(zhuǎn)移數(shù),這樣便求得1步轉(zhuǎn)移矩陣.
做n次方后的矩陣,第1行中屬于合法狀態(tài)的元素之和即為解.
禁止單詞總長度不超過100,因此合法狀態(tài)亦<100.總復(fù)雜度100^3*logN
zju3228(中) Searching the String 后綴數(shù)組,AC自動機,trie圖
原串長10^5, 現(xiàn)在有10^5次查詢, 每次查詢一個長度<=6的模式串在原串中的最大匹配次數(shù).
模式串的匹配方式有可重疊和不可重疊兩種, 需針對查詢的類型返回相應(yīng)值.
后綴數(shù)組解法(在線):
對原串建立sa和height數(shù)組.由于模式串長度最大只有6, 我們可以將height數(shù)組分別按L=1..6分組,預(yù)處理求出相應(yīng)長度每組內(nèi)不重疊子串的最大匹配次數(shù),此過程O(6*nlogn).
另外由于sa數(shù)組將所有后綴按字典序排好了,所以對一個詢問, 可以二分找到它在sa中第一次出現(xiàn)的位置p1和最后一次出現(xiàn)的位置p2, 則p2-p1+1就是可重疊匹配的答案. 對不可重疊匹配,只需直接返回p1處預(yù)處理時的值. 每次查詢O(logn).
trie圖,AC自動機解法(離線):
把所有查詢建trie圖, 對圖中的每個有效結(jié)點維護:該串長度,兩類查詢的計數(shù),該串上一次被匹配的位置, 還要用個鏈表記下這個串屬于哪些查詢.
剩下的就是經(jīng)典的自動機多串匹配了.
(*)關(guān)于棧掃:
height數(shù)組具有區(qū)間性,各個不同前綴被相應(yīng)的極小值隔開,而一個區(qū)間中又有多個子區(qū)間.各區(qū)間值大于區(qū)間端點的部分互不影響.因此可以維護一個存放height值不減的棧,棧中每個元素的附屬值, 記錄了它在棧中相鄰的兩個元素為端點的連續(xù)區(qū)間內(nèi)所有height值不小于它的必要信息.比如此題要記錄height>=k的連續(xù)區(qū)間內(nèi)sa[i] 的最大值和最小值.
棧掃描的經(jīng)典例子移步pku2559.
(**)trie圖備忘:
比trie樹多了個后綴指針psuf. 設(shè)當(dāng)前結(jié)點字母為c, 則psuf指向父親的后綴的pch[c].
trie樹中的后代結(jié)點指針pch(已經(jīng)更名為狀態(tài)轉(zhuǎn)移指針),當(dāng)相應(yīng)后代存在時,指向后代;否則指向當(dāng)前結(jié)點的后綴的相應(yīng)后代,即pch[k]=node[pa].pch[k].
后綴指針: 在接下來的狀態(tài)轉(zhuǎn)移中,當(dāng)前結(jié)點與它的后綴結(jié)點等價.
后代結(jié)點指針: 在當(dāng)前狀態(tài)下,接收到字符ch時,轉(zhuǎn)移到pch[ch]指向的結(jié)點.
posted on 2009-07-16 19:10
wolf5x 閱讀(1556)
評論(2) 編輯 收藏 引用 所屬分類:
acm_icpc