专栏首页Zaqdt_ACMHDU 1686 Oulipo(KMP)

HDU 1686 Oulipo(KMP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1686

题意是输入一个模式串p,再输入一个文本串s,问p在s中出现了多少次。

KMP的裸题


AC代码:

#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
char s[maxn], p[10005];
int Next[10005];
int T, ans;

void init(){
    int j = 0, k = -1;
    int len = strlen(p);
    memset(Next, -1, sizeof(Next));
    while(j < len){
        if( k == -1 || p[j] == p[k]){
            k ++;
            j ++;
            Next[j] = k;
        }
        else k = Next[k];
    }
}

void kmp(){
    int i = 0, j = 0;
    int l1 = strlen(p);
    int l2 = strlen(s);
    while(j < l2){
        if(i == -1 || p[i] == s[j]){
            i ++;
            j ++;
        }
        else{
            i = Next[i];
        }
        if(i == l1){
            i = Next[i];
            ans ++;
        }
    }
}

int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%s%s", p, s);
        init();
        ans = 0;
        kmp();
        printf("%d\n", ans);
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 2087 剪花布条(裸KMP)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Ch_Zaqdt
  • 2018年第九届蓝桥杯B组题解

    按着题目把这些数转换成8字节的二进制数就可以了,负数的二进制是补码。可以自己写个函数实现一下,实际效果图:

    Ch_Zaqdt
  • POJ 2752 Seek the Name, Seek the Fame(KMP求公共前后缀)

    题意是给了一个字符串,求出前i位的前缀刚好是后i位的后缀,输出这些位置,比如abcab当i为2的时候前缀为ab后缀也为ab

    Ch_Zaqdt
  • HDU 2087 剪花布条(裸KMP)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Ch_Zaqdt
  • C++11模板:如何判断类中是否有指定名称的成员变量?

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • Hdu 2612 Find a Way(双点bfs)

           题意代码最后的注释里有,这道题就是对两个人分别进行bfs搜索,然后记录下这两个人到每一家KFC的步数,最后遍历地图求出最少的步数,思路很简单,但实...

    Ch_Zaqdt
  • BZOJ2763: [JLOI2011]飞行路线(分层图 最短路)

    建\(k+1\)层图,对于边\((u, v, w)\),首先在本层内连边权为\(w\)的无向边,再各向下一层对应的节点连边权为\(0\)的有向边

    attack
  • 2016广东工业大学新生杯决赛网络同步赛暨全国新生邀请赛 题解&源码

    Problem A: pigofzhou的巧克力棒 Description 众所周知,pigofzhou有许多妹子。有一天,pigofzhou得到了一根巧克力棒...

    Angel_Kitty
  • 入行十余载,一字一句敲出数控行业的经验和总结

    A:思路:  先知道工件大小  -- 开粗刀具直径--二次开粗清角直径--要不要再次清角--中光平面----中光外形--光平面,大刀小刀光外形凸或凹  --清角...

    UG数控编程
  • 1024 科学计数法 (20 分)

    科学计数法是科学家用来表示很大或很小的数字的一种方便的方法,其满足正则表达式 [+-][1-9].[0-9]+E[+-][0-9]+,即数字的整数部分只有 1 ...

    可爱见见

扫码关注云+社区

领取腾讯云代金券