青竹qingzhu

后缀数组

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / 后缀数组（共1篇）

LightOJ - 1428Melody Comparison KMP+后缀数组

题意给A,B两个串，求有多少个A的不同的子串t，t中没有B这个子串。思路定义一个数组num，num[i]表示A字符串从i开始的A的子串能延伸到最右边的不包含B串的长度，其实就是从i开始向右的字符串不包含B的有多少个。所以sigma(num[i])就是答案的一部分了，又因为这样算出来的可能会有...

2020-07-13

0 460