前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 1711 Number Sequence(KMP)

HDU 1711 Number Sequence(KMP)

作者头像
Ch_Zaqdt
发布2019-10-22 18:10:32
3150
发布2019-10-22 18:10:32
举报
文章被收录于专栏:Zaqdt_ACM

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

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

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


AC代码:

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/10/09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档