冒泡ioa
冒泡ioa

后缀数组/后缀自动机
文章归档

[HAOI2016]找相同字符(后缀数组)

题目链接 题解 最近学后缀数组学得有点晕,还是要多练啊。 题目就一句话:求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 根据容斥原理,只要分别求出两个子串合并后的答案和两个子串单独的答案,最后的答案就是它们相减。 问题的关键就是如何在…

   305   2019-05-05   去围观

[CF427D]Match & Catch(后缀数组)

题目链接 题解 题目大意:求最小不重复相同子串。 考虑把两个字符串合并起来,求出sa,rk和Height数组。 我们可以从小到大枚举子串长度k,然后再枚举后缀。 具体来说,我们是根据子串字典序从小到大枚举后缀的 如果Height[i]不小于k(即第i-1个子串和第i个子串的…

   300   2019-05-03   去围观