hdu 1686 Oulipo(简单KMP)只不过比赛的时候用了string.一直超时,改成char就一遍AC,纠结。。。

本文主要是介绍hdu 1686 Oulipo(简单KMP)只不过比赛的时候用了string.一直超时,改成char就一遍AC,纠结。。。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、http://acm.hdu.edu.cn/showproblem.php?pid=1686

2、题目大意:

这道题目太纠结了,就是一道直接用KMP模板的题目,比赛的时候居然第一次想成做for循环次的KMP,超时了,后来知道只能用一次KMP了,结果用的string 一直超时,后来改成char居然一遍AC,还得好好熟悉算法

题目是给出两个字符串a,b,求a在b中出现多少次

3、题目:

Oulipo

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3999    Accepted Submission(s): 1578


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

Source
华东区大学生程序设计邀请赛_热身赛

Recommend
lcy   |   We have carefully selected several similar problems for you:   1358  1711  3336  3746  2203

4、AC代码:
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
char s[1000005];
char a[10005];
char b[1000005];
int f[10005];
void getFail(char p[], int *f)
{int m=strlen(p);f[0]=f[1]=0;for(int i=1; i<m; ++i){int j=f[i];while(j && p[i]!=p[j])j=f[j];f[i+1] = p[i]==p[j]?1+j:0;}
}
int find(char T[],char p[],int *f)
{getFail(p,f);int n=strlen(T);int m=strlen(p);int j=0;int sum=0;for(int i=0; i<n; ++i){while(j && T[i]!=p[j])j=f[j];if(T[i]==p[j])++j;if(j==m){sum++;}}return sum;
}
int main()
{int n;scanf("%d",&n);while(n--){scanf("%s",a);scanf("%s",b);int la=strlen(a);int lb=strlen(b);int sum=find(b,a,f);printf("%d\n",sum);}return 0;
}


附string 超时代码:

#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
char s[1000005];
string a;
string b;
int f[10005];
void getFail(string p, int *f)
{int m=p.length();f[0]=f[1]=0;for(int i=1; i<m; ++i){int j=f[i];while(j && p[i]!=p[j])j=f[j];f[i+1] = p[i]==p[j]?1+j:0;}
}
int find(string T,string p,int *f)
{getFail(p,f);int n=T.length();int m=p.length();int j=0;int sum=0;for(int i=0; i<n; ++i){while(j && T[i]!=p[j])j=f[j];if(T[i]==p[j])++j;if(j==m){sum++;}}return sum;
}
int main()
{int n;cin>>n;while(n--){cin>>a;cin>>b;int la=a.length();int lb=b.length();int sum=find(b,a,f);//printf("%d\n",sum);cout<<sum<<endl;}return 0;
}


这篇关于hdu 1686 Oulipo(简单KMP)只不过比赛的时候用了string.一直超时,改成char就一遍AC,纠结。。。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369649

相关文章

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

java实现延迟/超时/定时问题

《java实现延迟/超时/定时问题》:本文主要介绍java实现延迟/超时/定时问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java实现延迟/超时/定时java 每间隔5秒执行一次,一共执行5次然后结束scheduleAtFixedRate 和 schedu

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

Feign Client超时时间设置不生效的解决方法

《FeignClient超时时间设置不生效的解决方法》这篇文章主要为大家详细介绍了FeignClient超时时间设置不生效的原因与解决方法,具有一定的的参考价值,希望对大家有一定的帮助... 在使用Feign Client时,可以通过两种方式来设置超时时间:1.针对整个Feign Client设置超时时间

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要