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