POJ 3461 Oulipo 【KMP统计子串数】
传送门:http://poj.org/problem?id=3461
Oulipo
Description The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book:
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. Input The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
Output For 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 Sample Output 1 Source |
KMP模板:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = 1e6+;
const int MAXW = 1e4+;
char W[MAXW], T[MAXN];
int wlen, tlen;
int nxt[MAXW]; void get_Next()
{
int j = , k = -;
nxt[] = -;
while(j < wlen){
if(k == - || W[j] == W[k]){
nxt[++j] = ++k;
}
else k = nxt[k];
}
} int KMP_count()
{
int ans = , j = ;
if(wlen == && tlen == ){
if(W[] == T[]) return ;
else return ;
}
get_Next();
for(int now = ; now < tlen; now++){
while(j > && T[now] != W[j])
j = nxt[j];
if(W[j] == T[now]) j++;
if(j == wlen){
ans++;
j = nxt[j];
}
}
return ans;
} int main()
{
int T_case;
scanf("%d", &T_case);
while(T_case--){
scanf("%s%s", &W, &T);
wlen = strlen(W);
tlen = strlen(T); printf("%d\n", KMP_count());
}
return ;
}
最新文章
- 餐厅点餐系统app总结
- ECMAScript对文件夹图片幻灯片播放
- 通过定位position=";fixed";实现网页内容的固定层效果
- IE/Firefox每次刷新时自动检查网页更新,无需手动清空缓存的设置方法
- js一些算法实现
- ♫【模式】Curry化
- wordpress 设置头像
- 响应式网站-全屏banner响应的2中方法 - 被吃掉的banner
- spring cloud 入门系列三:使用Eureka 搭建高可用服务注册中心
- maven笔记学习
- BZOJ2434 [NOI2011] 阿狸的打字机 【树链剖分】【线段树】【fail树】【AC自动机】
- MVC面试问题与答案
- c#实现windows远程桌面连接程序代码
- [LeetCode] Palindrome Permutation I &; II
- 2016.6.17——Valid Parentheses
- 【BZOJ5083】普及 单调栈+二分+RMQ
- windchill10.0&;11.0API_chm版百度云
- 139.00.003 Git学习-Git时光机之Inbox体系(三)
- js中各种距离clientWidth
- 第2条:遵循PEP8风格指南
热门文章
- CentOS 7安装zabbix3.0
- lua实现List及Dictionary
- JDBC的PreparedStatement启动事务使用批处理executeBatch()
- struts 2 报错Could not find action or resul 常见错误原因分析
- JS常用的设计模式(6)——桥接模式
- [转]Wrapping multiple calls to SaveChanges() in a single transaction
- node.js获取cookie
- 通过tomcat shutdown port关闭tomcat
- hdu 3255 体积并
- mysql 乱码问题的捣鼓