题解：AT_abc433_c [ABC433C] 1122 Substring 2

· · 题解

题目传送门。

思路

根据题目要求序列的定义，要找一个满足要求的序列，需要找到一个 0 \le i < |S|-1 使得 S_i=S_{i+1}-1，只有这样的 i 才能产生满足要求的序列。接着不断向外扩展序列的左右端点，根据定义，如果新的左端点和右端点一直和最初的左端点和右端点相等，每延长一次就有一个新的序列。

例如，输入字符串为111222，可找到 i=2，不断向外扩展，有12 1122 111222三个序列。

代码

循环 i 从 0 到 |S|-2，如果 i 满足条件，就进入内层扩展循环，i 就可以充当子序列的右端点，因为在右端点扫过的区间值全部相等，不可能成为合法的 i。

在内层扩展完毕后，i 指向第一个不满足条件的元素，需要减 2，第一次退回最后一个满足条件的元素，由于它可能是合法的 i，因此需要再减一次，让外层循环将 i 加一，读者自证不难。

时间复杂度为 O(|S|)。