感覺都挺好玩的。

不會都寫。會都不寫。

Border 論做法

border 可以被劃分成 log 個等差數列。配合 dbf 表等性質可以存儲下整個子串的 border。

復雜度 \(O(n\log n)\)，是最優的做法。不建議在沒對 SA 和 border 論有充分理解的情況下使用。

鏈分治做法

基于 parent tree。

你需要兩種刻畫方式。

第一個方式是 border 是前綴的后綴。于是從 r 開始往上跳，找 endpos 集合內的值。

第二個方式是 border 相當于取一個 \([l,r)\) 內的前綴使得最長公共后綴不比前面部分小。

最長公共后綴這種東西容易想到就是 parent tree 上的 lca。

于是從根向 r dfs，統計其余子樹的貢獻。容易想到提前預處理出來。

雖然兩個方式復雜度都不對但是一個是現求一個是預處理不是感覺很能平衡嗎？

鏈分治，r 向上跳的過程中除了輕邊上的重兒子，其它的結點都是遍歷自己的輕子樹。輕子樹和是 \(O(n\log n)\) 的，可以預處理。

輕邊上的重兒子只有 \(\log n\) 個，使用方式一即可。

這種做法的另一種實現是點分治。

DAG 鏈剖分

開始大炮打蚊子。

類似樹剖，任意一條路徑輕邊數量可以保證。

令 \(f_i\) 為以 \(i\) 為終點的路徑數，\(g_i\) 為以 \(i\) 為起點的路徑數。\((u,v)\) 是重邊當且僅當 \(u\) 是 \(v\) 入點中 \(f\) 最大的，\(v\) 是 \(u\) 出點中 \(g\) 最大的。

不難證明剖出來的是鏈。并且每次 \(f\) 或 \(g\) 其中一定會有一個減半，所以只有 \(\log V\) 條輕邊。\(V\) 為路徑條數。

這個除了 SAM 還真不知道有什么用的到。

border 的一種刻畫方式：\([1,r]\) 的所有后綴與 \([l,n]\) 的所有前綴的交。前者跳 parent tree 的祖先鏈，后者即 SAM 上一條到 \(l\) 的鏈。

基本子串結構

鏈接

當然也可以看原掄文。核武器轟草履蟲。應該是這里面最泛用的解法。

根號分治

四種求法有五個很正常吧。

border 小的時候可以 hash check，大的時候考慮本質不同的 border 不會很多。

暫咕。