向后缀数组的更深一步探索:SA-IS

最近训练发现字符串的题因为我太菜了几乎都做不出来,便打算重拾这个数据结构。 之前一直学的是倍增法,但是倍增O(nlogn)嘛。。emmm,怎么看都觉得会被卡XD 然鹅又听说过之前有过题目会卡O(n)的DC3而倍增却能过。。神奇 而SA-IS(Suffix Array-Induce Sort)是一个比…

poj2774:对后缀数组的复仇,O(nlog n)做法

话说上次发了一篇文章..A掉了2774这道水题,但是!用的是O(nlog^2 n)做法,有些不服.. 于是本人又研究了一次后缀数组的O(nlog n)做法,终于在昨晚领悟了!特A一题..终于可以教会师弟师妹们这一种数据结构了..哭 直接上代码吧..

poj2774:后缀数组之殇

不知道用这样的标题合不合适..总而言之,在我被后缀数组折磨了十余天后,我终于掌握了一种非主流的做法:O(nlog^2 n)构造法..在此我对在《高级数据结构》中介绍的后缀数组构造代码有很深的疑问..因为我发现我对着模板打出来的程序根本无法算出正确的后缀数组..晕 于是我使用的是《挑战程序设计竞赛》中…