B - Oulipo
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces.
So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.
InputThe first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.
OutputFor every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
#define MAXN 1000001
typedef long long LL;
/*
KMP 查找子串出现的次数
*/
char s[MAXN],t[MAXN];
int Next[MAXN];
void pre_kmp(int m)
{
int j,k;
j = ;k = -;Next[] = -;
while(j<m)
if(k==-||t[k]==t[j])
Next[++j] = ++k;
else
k = Next[k];
}
int KMP(char s[],char t[],int n,int m)
{
int i,j,ans;
i = j = ans = ;
if(n==&&m==)
return (s[]==t[])?:;
pre_kmp(m);
for(i=;i<n;i++)
{
while(j>&&s[i]!=t[j])
j = Next[j];
if(s[i]==t[j])
j++;
if(j==m)
{
ans++;
j = Next[j];
}
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",t,s);
printf("%d\n",KMP(s,t,strlen(s),strlen(t)));
}
}
最新文章
- win10电脑优化
- 关于js中闭包的理解
- 【GoLang】golang 微服务框架 介绍
- linux初始化配置-----网络配置
- 高性能jdbc封装工具 Apache Commons DbUtils 1.6(转载)
- matlab 函数说明--waitforbuttonpress
- RMI入门教程
- 知方可补不足~用xsl来修饰xml
- CSS3:优雅地绘制不规则ICON
- java 构造函数是如何执行的
- 编辑sass报错:error style.scss (Line 3: Invalid GBK character ";\xE5";)解决办法
- windows Tomcat+Nginx 集群 迷你版
- C# winform页面可视化设计打开失败,提示未能加载程序集或他的一个依赖项,dll错误
- SQL 是一门美丽的语言 她来自艺术
- JVM入门
- Windows2008/2012/2016多用户同时远程连接终端服务授权
- Prometheus监控学习笔记之PromQL操作符
- Can’t call setState (or forceUpdate) on an unmounted component 警告处理方法
- elementUI 通用确认框
- 解决php7.1的中遇到的问题