[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