hdu 1686 Oulipo【kmp】

简介: Problem Description The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'.
Problem 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:

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.

 

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:

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.
 

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 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN
 

Sample Output
 
 
1 3 0
 
题目翻译:看样例吧,没什么翻译的

#include <cstdio>
#include <cstring>
#define maxn 10005
int next[maxn], len1, len2;
char str[maxn], buf[maxn * 100];
void getNext() {
    len1=strlen(str);
    len2=strlen(buf);
	int i = 0, j = -1;
	next[i] = j;
	while(i < len1) {
		if(j == -1 || str[i] == str[j]) {
			++i; ++j;
            next[i] = j;
		}
		else j = next[j];
	}
}
int KMP() {
	getNext();
	int i = 0, j = 0, cnt = 0;
	while(i < len2) {
		if(j == -1 || buf[i] == str[j]) {
			++i; ++j;
			if(j == len1) cnt++;
		}
		else j = next[j];
	}
	return cnt;
}
int main() {
    int T;
    scanf("%d",&T);
	while(T--) {
        scanf("%s%s",str,buf);
		printf("%d\n",KMP());
	}
	return 0;
}

目录
打赏
0
0
0
0
2
分享
相关文章
[UDS] --- TesterPresent 0x3E
[UDS] --- TesterPresent 0x3E
377 1
Go语言中json序列化的一个小坑,建议多留意一下
在Go语言开发中,JSON因其简洁和广泛的兼容性而常用于数据交换,但其在处理数字类型时存在精度问题。本文探讨了JSON序列化的一些局限性,并介绍了两种替代方案:Go特有的gob二进制协议,以及msgpack,两者都能有效解决类型保持和性能优化的问题。
191 7
|
11月前
[HNCTF 2022 WEEK2]getflag-入土为安的二十一天
[HNCTF 2022 WEEK2]getflag-入土为安的二十一天
94 0
|
4月前
|
SQL
【YashanDB知识库】通过触发器复制varchar(4000 char)列的数据导致乱码
【YashanDB知识库】通过触发器复制varchar(4000 char)列的数据导致乱码
C语言中的浮点数存储:深入探讨
C语言中的浮点数存储:深入探讨
千亿大模型来了!通义千问110B模型开源,魔搭社区推理、微调最佳实践
近期开源社区陆续出现了千亿参数规模以上的大模型,这些模型都在各项评测中取得杰出的成绩。今天,通义千问团队开源1100亿参数的Qwen1.5系列首个千亿参数模型Qwen1.5-110B,该模型在基础能力评估中与Meta-Llama3-70B相媲美,在Chat评估中表现出色,包括MT-Bench和AlpacaEval 2.0。
【C++高阶】C++继承学习手册:全面解析继承的各个方面
【C++高阶】C++继承学习手册:全面解析继承的各个方面
101 1
前端开发中的响应式设计原则与实践
【2月更文挑战第2天】本文探讨了前端开发中的响应式设计原则与实践。首先介绍了什么是响应式设计,以及它在现代网页设计中的重要性。接着,详细讨论了几种常用的响应式设计原则,包括流式布局、媒体查询和弹性图片等。最后,通过一个实例演示了如何利用CSS和JavaScript来实现响应式设计。本文旨在帮助前端开发者理解和应用响应式设计,提升网页的用户体验。
Python实现划分数组为连续数字的集合
Python实现划分数组为连续数字的集合
211 0
AI助理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问

你好,我是AI助理

可以解答问题、推荐解决方案等