题号：NC215138
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Kotori has just learnt the Knuth-Morris-Pratt algorithm in the algorithm course and would like to give the following problem a try:
Find the total number of occurrence of the strings "cat" and "dog" in a given string
.
As Kotori is not familiar with the KMP algorithm, she turns to you for help. Can you help Kotori solve this problem?
Find the total number of occurrence of the strings "cat" and "dog" in a given string
As Kotori is not familiar with the KMP algorithm, she turns to you for help. Can you help Kotori solve this problem?
输入描述:
There is only one test case in each test file.
The first and only line contains a string) which only contains lower-cased English letters.
输出描述:
Output one line containing one integer indicating the total number of occurrence of "cat" and "dog" in the string.
备注:
For the first sample test case, there are 3 "cat" and 1 "dog" in the string, so the answer is 4.
For the second sample test case, there is only 1 "cat" and no "dog" in the string, so the answer is 1.