专栏首页Zaqdt_ACMHDU 1711 Number Sequence(KMP)

HDU 1711 Number Sequence(KMP)

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

题意是输入两个数组,问能不能在文本数组s中找到模式数组p,输出最先的位置,如果找不到输出-1

思路就是kmp把字符串换成数组就好了,最后返回的是文本串中的位置减去模式串的长度,就是要求的最开始的位置。


AC代码:

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

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

int kmp(){
    int i = 0, j = 0;
    while(j < n){
        if(i == -1 || p[i] == s[j]){
            i ++;
            j ++;
        }
        else{
            i = Next[i];
        }
        if(i == m){
            return j - m;
        }
    }
    return -1;
}

int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%d", &s[i]);
        for(int i=0;i<m;i++)scanf("%d", &p[i]);
        init();
        int ans = kmp();
        printf("%d\n", ans == -1 ? ans : ans + 1);
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NYOJ 116 士兵杀敌(二) (线段树+树状数组)

    题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=116

    Ch_Zaqdt
  • 最少联通代价(dfs+曼哈顿距离)

    现在要把这 2 个连通块连通, 求最少需要把几个’.’转变成’X’。上图的例子中, 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点...

    Ch_Zaqdt
  • 牛客练习赛33 D. tokitsukaze and Inverse Number(逆序数定理)

    题目链接:https://ac.nowcoder.com/acm/contest/308/D

    Ch_Zaqdt
  • BZOJ4773: 负环(倍增Floyd)

    一个很显然的思路(然而我想不到是用\(f[k][i][j]\)表示从\(i\)号点出发,走\(k\)步到\(j\)的最小值

    attack
  • 洛谷P1730 最小密度路径(floyd)

    很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

    attack
  • 洛谷P1941 飞扬的小鸟(背包 dp)

    很显然的dp,设\(f[i][j]\)表示第\(i\)个位置,高度为\(j\)的最小步数

    attack
  • 洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows(bitset Floyd)

    显然如果题目什么都不说的话需要\(\frac{n * (n - 1)}{2}\)个相对关系

    attack
  • LWC 66: 760. Find Anagram Mappings

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • HDU5036 Explosion(期望 bitset)

    首先根据期望的线性性,可以转化为求每个点的期望打开次数,又因为每个点最多会被打开一次,只要算每个点被打开的概率就行了

    attack
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    刘晓杰

扫码关注云+社区

领取腾讯云代金券