POJ-3461-Oulipo

ACM模版

描述

题解

KMPKMP 入门级题目,模板题。

代码

#include <iostream>

const int MAXN = 1e4 + 10;
const int MAXM = 1e6 + 10;

void KMP_Pre(char x[], int m, int next[])
{
    int i = 0, j = next[0] = -1;
    while (i < m)
    {
        while (-1 != j && x[i] != x[j])
        {
            j = next[j];
        }
        next[++i] = ++j;
    }
}

int n;
int nxt[MAXN];
char W[MAXN];
char T[MAXM];

int KMP_Count(char x[], int m, char y[], int n)
{
    int i, j, ret = 0;

    KMP_Pre(x, m, nxt);

    i = j = 0;
    while (i < n)
    {
        while (-1 != j && y[i] != x[j])
        {
            j = nxt[j];
        }
        i++;
        j++;
        if (j >= m)
        {
            ret++;
            j = nxt[j];
        }
    }

    return ret;
}

int main(int argc, const char * argv[])
{
    scanf("%d", &n);

    while (n--)
    {
        scanf("%s%s", W, T);

        int m = (int)strlen(W);
        int n = (int)strlen(T);

        printf("%d\n", KMP_Count(W, m, T, n));
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MasiMaro 的技术博文

windows 安全模型简介

操作系统中有些资源是不能由用户代码直接访问的,比如线程进程,文件等等,这些资源必须由系统级代码由RING3层进入到RING0层操作,并且返回一些标识供用户程序使...

2472
来自专栏JackieZheng

探秘Tomcat——启动篇

tomcat作为一款web服务器本身很复杂,代码量也很大,但是模块化很强,最核心的模块还是连接器Connector和容器Container。具体请看下图: ? ...

4857
来自专栏alexqdjay

SpringCloud 之 Zuul 源代码详细笔记

5818
来自专栏跟着阿笨一起玩NET

C# 地磅串口编程

然后最近有一个项目用到了地磅,这里也是通过串口通讯方式进行数据交互,说实话,地磅这东西,实在有点不方便。

1872
来自专栏Fish

CUDA C最佳实践-CUDA Best Practices(二)

9. 内存优化 看页数也知道,内存优化是性能提升最重要的途径。目标在于通过最大化带宽获得对硬件的最大使用率。最好使用快速内存而减少慢速内存的访问。这章就是各种讨...

33610
来自专栏崔庆才的专栏

Scrapy框架的使用之Scrapy对接Selenium

6144
来自专栏Java3y

ThreadLocal就是这么简单

1466
来自专栏LEo的网络日志

python技巧分享(十三)

2653
来自专栏吴生的专栏

SpringCloud源码:Ribbon负载均衡分析

可以看到,在整合 Ribbon 之前,请求Rest是通过IP端口直接请求。整合 Ribbon 之后,请求的地址改成了 http://applicationNam...

1040
来自专栏崔庆才的专栏

Scrapy 对接 Selenium

本节我们来看一下 Scrapy 框架中如何对接 Selenium,这次我们依然是抓取淘宝商品信息,抓取逻辑和前文中用 Selenium 抓取淘宝商品一节完全相同...

3.1K2

扫码关注云+社区

领取腾讯云代金券