唯一分割的结构：由于 $x$ 不含 $d$ 与 $p$ ，整串必然呈现反复的模式：一段由非 $d,p$ 字符构成的连续块 $x$ ，随后紧跟着 "dp"；如此反复直到串末。
线性扫描：从左到右扫描：
- 累积一段由非 $d,p$ 字符组成的连续块作为当前的 $x$ ；
- 读到 "dp" 后结束该段，将该 $x$ 放入集合；
- 跳过 "dp" 继续下一段。
正确性：每一段的 $x$ 恰为紧邻其后的 "dp" 之前的最长非 $d,p$ 连续块；由于 $x$ 不能含 $d,p$ 且分割唯一，上述扫描会精确得到每个 $x$ ，且不会遗漏或重复切分。

P3587.第1题-dp算法

1000ms

Difficulty: 3

所属公司 : 美团

算法与标签>字符串

题目内容

已知一套试卷包含多个 $x-dp$ 算法，即 $x$ 类型的 $dp$ (保证 $x$ 不为空且不含 $'d’$ 和 $'p’$ 两个字符)。例如 $sosdp$ ， $adp$ ，其拼接起来为 $sosdpadp$ ，构成了一套完整的试卷。

现在便可以得到该试卷中存在若干类型的 $dp$ 算法，你需要知道有多少种本质不同的 $dp$ 算法，即有多少种不同 $x$ 类型的算法。

保证 $s$ 可以被唯一地分割为一个或多个形如 $x+dp$ 的段。

在一行上输入一个仅由小写字母组成的字符串 $s(3≤length(s)≤ 10^6)$ ，表示试卷。

输出一个整数，表示给定试卷中存在多少种不同类型的 $dp$ 算法。

输入

sosdpadp

输出

输入

adpbdpadp

输出

输入

预期输出（选填）