hdu 1686 Oulipo kmp算法
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1686
题目:
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.
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.
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
3
0
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define PI acos((double)-1)
#define E exp(double(1))
#define K 1000000+9
int nt[+];
char a[K],b[];
//参数为模板串和next数组
//字符串均从下标0开始
void kmp_next(char *T,int *nt)
{
nt[]=;
for(int i=,j=,m=strlen(T);i<m;i++)
{
while(j&&T[i]!=T[j])j=nt[j-];
if(T[i]==T[j])j++;
nt[i]=j;
}
}
int kmp(char *S,char *T,int *nt)
{
kmp_next(T,nt);
int ans=,sn=strlen(S),tn=strlen(T);
for(int i=,j=;i<sn;i++)
{
while(j&&S[i]!=T[j])j=nt[j-];
if(S[i]==T[j])j++;
if(j==tn)
ans++;
}
return ans;
}
int main(void)
{
int t;cin>>t;
while(t--)
{
scanf("%s%s",b,a);
printf("%d\n",kmp(a,b,nt));
} return ;
}
最新文章
- 使用神经网络来识别手写数字【译】(三)- 用Python代码实现
- CSS列表逆序
- A 标签的背景
- AfNetworking 3.0源码解读
- Git - 使用指南
- JS中String类型转换Date类型 并 计算时间差
- 英文破折号(em dash)、连接号(en dash)与连字符(hyphen)的区别及各自用法是什么?
- 【源代码】基于Android和蓝牙的单片机温度採集系统
- java模拟浏览器包selenium整合了htmlunit,火狐浏览器,IE浏览器,opare浏览器驱
- 有一定基础的 C++ 学习者该怎样学习 Windows 编程?
- 阿里云API网关(18)请求报文和响应报文
- 优雅的启动、停止、重启你的SpringBoot项目
- WC.exe【C】
- 密码疑云 (3)——详解RSA的加密与解密
- Jury Compromise POJ - 1015 dp (标答有误)背包思想
- How Xtuner E3 works for BMW 520d Diagnosis and initialization of CBS service
- HDU6201
- python之命令行参数解析模块argparse
- CAFFE 调试
- iOS 获取已安装 的APP
热门文章
- PHP上传类 图片上传 upload class实现image crop resize 缩略图
- 快速排序的c++实现 和 python 实现
- C语言 百炼成钢26
- 【BZOJ】3432: [Usaco2014 Jan]Cross Country Skiing (bfs+二分)
- BestCoder Round #81 (div.2) 1004 String(动态规划)
- Jafka Broker代码阅读之总览
- ARM汇编语言(1)(基本概念)
- (转)java反编译i++和++i问题
- Mysql数据库存储是乱码问题(或者在查询时无法加载数据)
- Android无线测试之—UiAutomator UiScrollable API介绍一