NC215138. AlgorithmCourse
描述
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.
示例1
输入:
catcatcatdogggy
输出:
4
示例2
输入:
docadosfascat
输出:
1
示例3
输入:
icpcnanjing
输出:
0