ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

全部文章 / 题解（共2篇）

Luogu P3181 【[HAOI2016]找相同字符】

Description 传送门 Solution 这题就是让求两个串的相同子串的个数。众所周知，字符串所有的子串就是字符串所有的后缀的所有前缀。利用这个性质我们可以将问题转化，变成求两个字符串的所有后缀的\(lcp\)的长度的和。求后缀的\(lcp\)我们可以使用\(SA\)。...

单调栈 SA 字符串 Luogu

2020-06-12

0 374

BZOJ 3145 Str

Description 传送门 Solution 如果直接暴力的话，可以枚举那个不同的字符在串一和串二里的位置分别是什么，然后算一下他们的\(lcp\)和\(lcs\)来更新答案，也就是\(\sum_{i = 1, j = 1} ^{i <= n, j <= m} lcp(i ...

启发式合并字符串 SA BZOJ

2020-06-15

0 397