#P6805. [2020福建冬令营]黑红兔

    ID: 6628 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-线性 DP后缀数组倍增计数排序Kasai 算法LCP+RMQST 表二分查找可持久化线段树势能分析

[2020福建冬令营]黑红兔

题目描述

给定长度为 nn 的小写英文字母字符串 ss。选取 kk 个非空区间,满足

$$1\le l_1\le r_1<l_2\le r_2<\cdots<l_k\le r_k\le n.$$

记 s[l…r]s[l\ldots r] 为从第 ll 个到第 rr 个字符组成的连续子串。要求对每个 1≤i<k1\le i<k,s[li+1…ri+1]s[l_{i+1}\ldots r_{i+1}] 都是 s[li…ri]s[l_i\ldots r_i] 的严格子串。所谓严格子串,是从原串首尾分别删除一些字符,且总共至少删除一个字符后得到的连续子串。

求可选的最大 kk。

输入格式

一行一个字符串 ss。

输出格式

一行一个整数,表示最大的 kk。

样例

bbcb
2

可选区间 [1,2][1,2] 和 [4,4][4,4]。

abcdbcc
3

可选区间 [1,4][1,4]、[5,6][5,6]、[7,7][7,7]。

pinkrabbitpinkrtxdytxinkrdynkrabnknealchentxdy
6

数据范围

全部数据满足 1≤n≤5×1051\le n\le5\times10^5,字符串仅含小写英文字母。

子任务 nn 上限 分值
1 100 10
2 1000 15
3 3×1043\times10^4 25
4 10510^5 30
5 5×1055\times10^5 20

原题 PDF