HDU-1686-Oulipo

简介: HDU-1686-Oulipo



Oulipo

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 98   Accepted Submission(s) : 63

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

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

 


题目意思很明显了就是kmp  求第一个串在第二个里面出现几次 假如说主串是   a   b  a  b  a  b  c  d  a   b   a    b   a   b   h     f   a    b     a     b    a    b   子串是   ababab

                     

i    0   1  2  3  4  5  6  7  8   9  10  11 12 13 14  15 16  17   18   19   20   21

    a   b  a  b  a  b  c  d  a   b   a    b   a   b   h     f   a    b     a     b    a    b

                                     a   b   a    b   a   b

j                                   -1   0   0    1   2    3    4                                                                  

这是子串的跳转表

i   0   1    2    3   4    5    6

    a    b   a    b   a    b

j    -1   0   0    1   2    3    4


  点击这里   kmp详解



#include<cstdio>
#include<cstring>
const int M=10000+10;
char str2[M*100],str1[M];
int p[M];
int cnt,len1,len2;
void getp()
{
    int i=0,j=-1;
    p[i]=j;
    while(i<len1)
    {
        if(j==-1||str1[i]==str1[j])
        {
           i++;j++;
           p[i]=j;
        }
        else    j=p[j];
    }
}
void kmp()
{
    getp();
    int i=0,j=0;
    while(i<len2)
    {
        if(j==-1||str2[i]==str1[j])
        {
            i++;j++;
            if(j==len1) cnt++; // 每次查到匹配串长度是就说明出现了一个匹配串
        }
        else  j=p[j];
    }
}
int main()
{ 
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",str1,str2);
        len1=strlen(str1);
        len2=strlen(str2);
        cnt=0;
        kmp();
        printf("%d\n",cnt);
    }
    return 0;
}





目录
相关文章
|
算法 C++ 计算机视觉
区域生长算法 C++实现
在比赛和项目中用opencv用多了,就会发现很多opencv没有实现的算法,其中一些还是十分常用,在教科书上经常出现的。作为一个弱鸡,有的简单的算法能够自己实现(比如本文所要讲的),有的写到一半就打出GG,有的直接就下不了手。
2077 0
|
存储 JSON 负载均衡
Token、Session、Cookies是什么?如何理解其不同?一文带你了解
这篇文章详细解释了Token、Session和Cookies的概念、作用及其区别,探讨了它们在维持HTTP无状态连接中用户状态的用途和优缺点,特别是Session的服务器端存储和Token的客户端存储特性,以及它们在不同场景下的应用。
Token、Session、Cookies是什么?如何理解其不同?一文带你了解
|
9月前
|
人工智能 弹性计算 运维
操作系统控制台,让运维更简单!
操作系统控制台初体验,运维智能666!
353 37
操作系统控制台,让运维更简单!
|
API 算法框架/工具
【threejs教程】三维物体与三维向量
【8月更文挑战第7天】threejs教程:三维物体与三维向量
260 3
【threejs教程】三维物体与三维向量
|
消息中间件 存储 负载均衡
分布式消息传递新时代:深入了解RabbitMQ_sharding插件的精髓【RabbitMQ 八】
分布式消息传递新时代:深入了解RabbitMQ_sharding插件的精髓【RabbitMQ 八】
329 0
|
运维 安全 Linux
计算机架构“寒武纪爆发”,操作系统进化迸发中国浪潮
计算机架构“寒武纪爆发”,操作系统进化迸发中国浪潮
|
自然语言处理 数据处理 Python
【Python】已解决:ModuleNotFoundError: No module named ‘LAC‘
【Python】已解决:ModuleNotFoundError: No module named ‘LAC‘
223 0
详尽分享电脑win键没有反应(最全方案)
详尽分享电脑win键没有反应(最全方案)
599 0
|
存储 JavaScript
MATLAB实战 | 求矩阵指数、预定义变量i和j的含义以及梯形积分法
MATLAB实战 | 求矩阵指数、预定义变量i和j的含义以及梯形积分法
429 0
MATLAB实战 | 求矩阵指数、预定义变量i和j的含义以及梯形积分法