ZOJ 17届校赛 Knuth-Morris-Pratt Algorithm( 水题)
In computer science, the Knuth-Morris-Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
Edward is a fan of mathematics. He just learnt the Knuth-Morris-Pratt algorithm and decides to give the following problem a try:
Find the total number of occurrence of the strings "cat" and "dog" in a given string s.
As Edward is not familiar with the KMP algorithm, he turns to you for help. Can you help Edward to solve this problem?
Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 30), indicating the number of test cases. For each test case:
The first line contains a string s (1 ≤ |s| ≤ 1000).
Output
For each case, you should output one integer, indicating the total number of occurrence of "cat" and "dog" in the string.
Sample Input
7
catcatcatdogggy
docadosfascat
dogdddcat
catcatcatcatccat
dogdogdogddddooog
dcoagtcat
doogdog
Sample Output
4
1
2
5
3
1
1
Hint
For the first test case, there are 3 "cat" and 1 "dog" in the string, so the answer is 4.
For the second test case, there is only 1 "cat" and no "dog" in the string, so the answer is 1.
水题
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
using namespace std; char a[]; int main()
{
int T,len,sum,i;
while(~scanf("%d",&T))
{
while(T--)
{
scanf("%s",&a);
len=strlen(a);
sum=;
for(i=;i<len-;i++)
{
if(a[i]=='c'&&a[i+]=='a'&&a[i+]=='t')
sum++;
else if(a[i]=='d'&&a[i+]=='o'&&a[i+]=='g')
sum++;
}
printf("%d\n",sum);
}
}
return ;
}
最新文章
- 敏捷转型历程 - Sprint3 一团糟的演示会
- 读书笔记:const和readonly、static readonly 那些事
- MySQL高可用之MHA搭建
- MySql查询语句中解决“该列没有包含在聚合函数或者groupby子句中”的相关问题方法
- eclipse的一些初始化设置
- Linux-配置虚拟IP实例
- hpple 简单使用
- java操作properties配置文件
- 全球第一免费开源ERP Odoo Ubuntu最佳开发环境独家首发分享
- JS数组循环的性能和效率分析(for、while、forEach、map、for of)
- model.form使用,配合form的钩子
- Netty精粹之玩转NIO缓冲区
- PHP递归排序
- 动态加载JS函数
- SE93 创建参数事务
- <;邱永汉股票入门>;读书笔记
- linux服务器文件索引inodes满了
- RF - selenium - 常用关键字
- 设计模式之&mdash;&mdash;Observer模式
- NET怎么精确计算一个对象占用的内存空间(GMK)