CF1063F String Journey DP、SAM、线段树
2024-09-08 14:46:09
为了方便把串反过来，条件变为\(t_i\)是\(t_{i+1}\)的真子串，答案显然不变。
一件重要的事情是必定存在一种最优解，字符串序列\(\{t\}\)满足\(|t_i| = i\)。
考虑DP：设\(f_i\)表示字符串序列\(\{t\}\)的最后一个串的结尾位置为\(i\)时，\(|t|\)的最大值。不难发现如果\(f_i = x\)，那么一定存在最后一个串结尾位置为\(i\)、长度在\([1,x]\)内的字符串序列。
因为有\(f_i \leq f_{i-1}+1\)（因为对于一个能够满足序列长度为\(f_i\)、最后一个串结尾为\(i\)的字符串序列\(t\)，把第一个字符串删掉，然后把其他的串的最后一个字符删掉，就可以得到序列长度为\(f_i - 1\)、最后一个串结尾为\(i-1\)的一个合法的字符串序列），所以可以从大到小枚举\(f_i\)的合法取值，这里的总check次数是\(O(n)\)的。
那么问题变成如何check。考虑我们实际上只需要满足\(s_{1,i - f_i}\)中是否存在一个\(s_{i - f_i + 1 , i}\)的子串满足该串的结尾的\(f\)值大于等于\(f_i - 1\)。注意到可能满足条件的只有两个子串（\(s_{i - f_i + 1 , i - 1}\)和\(s_{i - f_i + 2 , i}\)），所以我们只需要知道这些点所有\(\leq i - f_i\)的endpos中的\(f\)值的最大值。注意到\(i - f_i\)是单调不降的，所以我们可以使用一个指针维护当前询问的前缀，在线段树上做单点修改、子树查询最大值即可。
最新文章
- centos python2.6升级到2.7 还有单独的python3.5环境
- 破解 “PEDIY CrackMe 2007” 之 KeygenMe_1_by_boonz
- 使用Node.js实现数据推送
- 为Eclipse设置背景色
- #Leet Code# LRU Cache
- 弹飞DZY（思维，打表，还没过全，先放着）
- 依赖于设备的位图(DDB) ,CreateCompatibleBitmap用法
- 【LeetCode】29. Divide Two Integers
- Chapter 1 First Sight——25
- react中文API解读一（快速开始）
- 【Webpack 杂谈】帮助文档翻译：Webpack的模块
- ng-model-options 时延
- Leetcode 记录（1~100）
- maven(一)：是否有必要使用maven
- 洛谷.3803.[模板]多项式乘法(FFT)
- JVM活学活用——GC算法 垃圾收集器
- JMeter安装+配置+运行
- Java8 Stream语法详解 2
- Webpack-simple cross-env 不是内部或外部命令问题处理
- Windows Phone 8/Windows 8 启动第三方应用程序并传递参数