思路

• 唯一分割的结构：由于 $x$ 不含 $d$ 与 $p$，整串必然呈现反复的模式：一段由非 $d,p$ 字符构成的连续块 $x$，随后紧跟着 "dp"；如此反复直到串末。

• 线性扫描：从左到右扫描：

  • 累积一段由非 $d,p$ 字符组成的连续块作为当前的 $x$；
  • 读到 "dp" 后结束该段，将该 $x$ 放入集合；
  • 跳过 "dp" 继续下一段。

• 正确性：每一段的 $x$ 恰为紧邻其后的 "dp" 之前的最长非 $d,p$ 连续块；由于 $x$ 不能含 $d,p$ 且分割唯一，上述扫描会精确得到每个 $x$，且不会遗漏或重复切分。

• 复杂度：时间 $O(n)$，空间 $O(k)$，其中 $n$ 为 $\text{length}(s)$，$k$ 为不同 $x$ 的数量。

题目内容

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

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

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

输入描述

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

输出描述

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

样例1

输入

sosdpadp

输出

2

样例2

输入

adpbdpadp

输出

2