The 17th Zhejiang University Programming Contest Sponsored by TuSimple J
Knuth-Morris-Pratt Algorithm
Time Limit: 1 Second Memory Limit: 65536 KB
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.
题意:很明显的
解法:KMP
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std;
char t[],s[];
int flink[];
void cmd(char *t)
{
int i=,j=-;
flink[]=-;
int len=strlen(t);
while(i<len)
{
if(j==- || t[i]==t[j])
flink[++i]=++j;
else
j=flink[j];
}
}
int sum(char *t,char *s)
{
int ans=;
int i=,j=;
int n=strlen(t);
int len;
len=strlen(s);
while(i<len)
{
if(j==- || s[i]==t[j])
{
++i;
++j;
}
else
{
j=flink[j];
}
if(j==n) ans++;
}
return ans;
}
int main()
{
int c;
scanf("%d",&c);
while(c--)
{
scanf("%s",s);
cmd("cat");
int a=sum("cat",s);
cmd("dog");
int b=sum("dog",s);
printf("%d\n",a+b);
}
return ;
}
最新文章
- 设计模式(十三) 职责链(chain of responsibility)
- python logging
- SignalR 2.1 简单入门项目
- MVC视图请求流程视图
- 用nodejs搭建一个简单的服务器
- IAR修改工程名称Tab键设置模板建立
- c语言函数传递数组
- Linux通过XAMPP集成软件包搭建LAMPP环境
- R与并行计算(转)
- mysql 多实例部署
- Linux - 常用 Linux 命令的基本使用
- HTML-XMLHttpRequest
- android摄像头(camera)之 v4l2的c测试代码【转】
- wxPython 入门开发示例
- cocos2d-x 3.0 在C++中调用lua函数
- 解决window.open被拦截问题
- s2选择框的全选和反选jQuery
- sublime填坑之旅: 格式代码, 缩进缩进
- 【postgresql的使用】
- ARP级ping命令:arping
热门文章
- 嵌入式开发之davinci--- 8168 question about capture PAL on 8168
- UOJ #35. 后缀排序[后缀数组详细整理]
- Marking as slave lost.
- js replace()实现全部替换
- redis03----link 链表操作
- Java 快速失败( fail-fast ) 安全失败( fail-safe )
- js运行机制及异步编程(一)
- mpvue——实现点击数组内的某一元素进行置顶(排序第一)操作
- jquery 获取radio被选中的值
- poj 1274 The Perfect Stall 解题报告