luogu模板 后缀排序 后缀数组

贴一个模板
虽然后缀平衡树是个好东西,但是写起来还是挺长的,而且同样是\(O(nlog_2n)\)和后缀数组比速度还是不太乐观
再写几个注意事项吧
– 后缀数组和后缀平衡树降低复杂度的思想一样,利用已经排好序的串的排名信息还加速比较过程
– \(x_i\)表示以\(s_i\)开头的一段字符串的排名,\(y_i\)表示的则是第二关键字排名为\(i\)的串的第一关键字的位置,这个弄错了就会很难受

发表评论

电子邮件地址不会被公开。 必填项已用*标注