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