[USACO21JAN] Uddered but not Herd G

题目描述

一个鲜为人知的事实是,奶牛拥有自己的文字:「牛文」。牛文由 26 个字母 'a' 到 'z' 组成,但是当奶牛说牛文时,可能与我们所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同,她会按某种特定的顺序排列字母。 为了打发时间,Bessie 的表妹 Mildred 在反复哼唱牛文字母歌,而 Farmer Nhoj 好奇她唱了多少遍。 给定一个小写字母组成的字符串,为 Farmer Nhoj 听到 Mildred 唱的字母,计算 Mildred 至少唱了几遍完整的牛文字母歌,使得 Farmer Nhoj 能够听到给定的字符串。Farmer Nhoj 并不始终注意 Mildred 所唱的内容,所以他可能会漏听 Mildred 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。 注意:本题每个测试点的时间限制为默认限制的两倍。

输入输出格式

输入格式


输入仅一行,包含一个小写字母组成的字符串,为 Farmer Nhoj 听到 Mildred 唱的字母。字符串的长度不小于 $1$ 且不大于 $10^5$。

输出格式


输出 Mildred 所唱的完整的牛文字母歌的最小次数。

输入输出样例

输入样例 #1

mildredree

输出样例 #1

3

说明

Mildred 至少唱了三遍牛文字母歌。有可能 Mildred 只唱了三遍牛文字母歌,如果牛文字母表以 "mildre" 开头,并且 Farmer Nhoj 听到了以下被标记为大写的字母。 ``` MILDREabcfghjknopqstuvwxyz milDREabcfghjknopqstuvwxyz mildrEabcfghjknopqstuvwxyz ``` #### 测试点性质: - 测试点 1-5 中,Farmer Nhoj 仅听到出现在 Mildred 或 Bessie 的名字中的字母。 - 测试点 6-16 中,Farmer Nhoj 从未听到任何出现在 Mildred 名字中的字母。 供题:Nick Wu,Brian Dean