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

相关文章

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 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

java String.join()的使用小结

《javaString.join()的使用小结》String.join()是Java8引入的一个实用方法,用于将多个字符串按照指定分隔符连接成一个字符串,本文主要介绍了javaString.join... 目录1. 方法定义2. 基本用法2.1 拼接多个字符串2.2 拼接集合中的字符串3. 使用场景和示例3

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.