expect2004

字符串 - 后...

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章 / 字符串 - 后缀数组（SA）（共3篇）

LG2463/BZOJ4698 「SDOI2008」Sandy的卡片后缀数组

问题描述 LG2463 BZOJ4698 题解看到\(n\)个数串，一开始不太好处理，可以很容易想到把这\(n\)个数串连到一起，形成一个大串，但是每个串之间不容易处理。经过思考，想到在每个串中间加一个不可能出现在原数串中的数，取\(2333\)。对大串做后缀数组，求\(\ma...

2019-09-08

0 325

LG2852/BZOJ1717 「USACO2006DEC」Milk Patterns 离散化+后缀数组

问题描述 LG2852 题解字符串性质：字符串\(s\)的每个字串等于每个后缀的所有前缀对输入的东西离散化，然后把数值看做\(\mathrm{ASCII}\)后缀排序二分答案，二分长度。显然一段相同的字串，一定是连续一段后缀的公共前缀。如此\(check\)即可。 ...

2019-09-08

0 328

LG4051/BZOJ1031 「JSOI2007」字符加密后缀数组

问题描述BZOJ1031LG4051 题解发现这是一个环，根据经验，破环为链，于是字符环变为了字符串之后对这个复制之后的字符串求后缀数组。$len$代表原字符串长度，代表复制后的字符串长度最后输出的时候，判断一下，如果$SA_i \le len$，则输出$str_i$。 Code ...

2019-09-06

0 323