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

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

阅读更多 →
代码
2016-08-08
poj1743:后缀数组+二分(1/8个男人,楼教主的男人八题)

给师弟讲课的时候讲了后缀数组,然后决定来A一题.. Musical Theme Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 26043 Accepted: 8803 Description A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but tr …

阅读更多 →
代码
2016-05-31
poj2774:对后缀数组的复仇,O(nlog n)做法

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

阅读更多 →
代码
2016-05-27
poj2774:后缀数组之殇

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

阅读更多 →
代码 学习
没有更多文章了...