冷滟泽的个人博客

2019-02-28 lengyanze 阅读(37) 评论(0)

题意 给出一个串 A 和 n 个串 Bi ，求 A 中不在任何一个 Bi 中出现的本质不同的子串的个数。 思路 后缀数组 + 单调栈; 把 A 和所有 Bi 拼接在一起，用间隔符分隔后做后缀排序并求出 height...

2019-02-24 lengyanze 阅读(71) 评论(0)

题意 给出一个长度为 n 的字符串 s 和 q 次询问，每次询问给出两个集合 A,B ，求 \sum_{i\in A}\sum_{j\in B} lcp(i,j) 思路 求后缀之间的 LCP 之和，自然地想到使用后...

2019-02-21 lengyanze 阅读(40) 评论(0)

题意 给出两个字符串 A, B ，求这两个字符串长度不小于 k 的公共子串的个数。两对公共子串不同当且仅当子串在字符串的位置不同。 思路 后缀数组 + 单调栈； 把两个字符串连接起来，中间用分隔符隔开，做后缀排序；...

2019-02-19 lengyanze 阅读(42) 评论(0)

题意 枚举字符串 s 的每一个本质不同的子串 ss ，令 cnt(ss) 为子串 ss 在字符串 s 中出现的个数，求 \sum \frac{cnt(ss)\times [cnt(ss)+1]}{2} 思路 将 s...

2018-12-16 lengyanze 阅读(98) 评论(0)

题目链接 BZOJ2754 Luogu2336 概述 本题解法众多，比如： AC 自动机 广义后缀自动机 后缀数组 + 莫队 ...... 这里我介绍一种新的解法：后缀数组 + ST 表 + 二分 +...