题解：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|)$。