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