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