POJ 3461:Oulipo
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 28155 | Accepted: 11251 |
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 textT,
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
KMP模板题,没有比这个更模板的了。。。
唯一要提醒自己的是最后模式串和原串走的时候j是一直往前走的,不回头!怎么就记不住,每次都是搞了两层循环,然后TLE,你这么搞之前搞的那个next数组有什么用,动脑袋想一想啊光速小子。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std; char moshi[10005];
char pipei[1000005]; int result;
int next_moshi[10005]; void get_next()
{
int i,j=-1;
int len=strlen(moshi);
next_moshi[0]=-1; for(i=0;i<len;)
{
if(j==-1||moshi[i]==moshi[j])
{
i++;
j++; if(moshi[i]==moshi[j])
{
next_moshi[i]=next_moshi[j];
}
else
{
next_moshi[i]=j;
}
}
else
{
j=next_moshi[j];
}
}
} void get_result()
{
int i=0,j=0; int len_pipei=strlen(pipei);
int len_moshi=strlen(moshi); while(j<len_pipei)
{
if(moshi[i]==pipei[j])
{
i++;
j++;
}
else
{
if(next_moshi[i]==-1)
{
i=0;
j++;
}
else
{
i=next_moshi[i];
}
}
if(i>=len_moshi)
{
result++;
i=next_moshi[len_moshi];
}
}
} int main()
{
int Test;
scanf("%d",&Test); while(Test--)
{
result=0; scanf("%s%s",moshi,pipei); get_next();
get_result(); cout<<result<<endl;
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- Java---Java的面试题(一)
- spring3.0结合Redis在项目中的运用
- Orchard 刨析:前奏曲
- hunnu 11313 无重复元素序列的最长公共子序列转化成最长递增子序列 求法及证明
- java.sql.SQLException: Can not issue executeUpdate() for SELECTs
- 在64位Win7操作系统中安装Microsoft Access Engine的解决方案
- 第四章 Struts2深入
- 一篇不错的Gibbs Sampling解释文章,通俗易懂
- iOS 开发之 Xcode installation failed invalid argument!
- 微信小程序 bug及解决方案
- SQLServer之触发器简介
- el-date-picker 快捷日期简单计算
- luogu P4916 魔力环
- Java基础知识总结--String、StringBuffer、StringBuilder
- Linux下终端录制工具-asciinema
- SQL Server 2016新特性:Temporal Table
- linux(centos 7) 下安装nodejs
- e831. 从JTabbedPane中删除一个卡片
- redis 配置文件redis.conf
- vim:将刚写的单词大写和单词的定义
热门文章
- Linux CentOS7 VMware 安装软件包的三种方法、rpm包介绍、rpm工具用法、yum工具用法、yum搭建本地仓库
- vue - 封装input
- Day3-K-Can you solve this equation? HDU2199
- 「SP1716」GSS3 - Can you answer these queries III
- SQL Server DATEADD() 函数 一步步使用教程
- python的super()以及父类继承
- 什么是IPFS?IPFS与区块链有什么关系
- css的响应式布局和动画
- CentOS 6.5(x86_32)下安装Oracle 10g R2
- NO2 pwd-touch-vim-vi-echo-重定向等命令