曾經(jīng)看過許XX的論文 不過沒有看懂
09年羅XX的論文比那篇容易理解的多
后綴數(shù)組果然是一個很強大的東西 有關(guān)字符串的問題 只要學好自動機和后綴數(shù)組基本都能解決了
與其說是后綴數(shù)組強大 不如說height數(shù)組強大 后綴數(shù)組的作用也就是方便求解height數(shù)組
使用height數(shù)組 大致有如下你個常用方法
1、分組:將height值大于等于k的分置一組 使得同組內(nèi)最長公共前綴>=k
2、二分:根據(jù)具體情況 一般都是二分答案
3、連接：將所有涉及到的字符串連在一起處理
還有一個神奇的性質(zhì):當循環(huán)節(jié)長度確定時 保證覆蓋是s[0],s[l],s[l*2]～～中的某連續(xù)兩個
posted on 2009-04-14 12:29
250 閱讀(3313)
評論(2) 編輯 收藏 引用 所屬分類:
oi