HDU - 1711 Number Sequence解题报告(KMP)

题目大意:

还是kmp魔板题,给你两串数,从一串中找出另一串,要是存在多个,就输出最先找到的位置。

代码:

#include<iostream>
#include<math.h>
#include<stdio.h>

using namespace std;
int a[1000500];
int c[10050];
int m,n;
int my_next[10050];

void get_my_next()
{
    int i=0,k=-1;
    my_next[0]=-1;
    while(i<m)
    {
        if(k!=-1&&c[i]!=c[k])
        {
            k=my_next[k];
            continue;
        }
        i++;k++;
        if(c[i]==c[k])my_next[i]=my_next[k];
        else my_next[i]=k;
    }
}

int my_kmp()
{
    int i=0,j=0;
    while(i<n)
    {
        if(j==-1||a[i]==c[j])
        {
            i++;j++;
        }
        else
        {
            j=my_next[j];
        }
        if(j==m)
        {
            return i-m+1;
        }
    }
    return -1;
}

int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        scanf("%d",&n);
        scanf("%d",&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d",&c[i]);
        }
        get_my_next();
        cout<<my_kmp()<<endl;
    }
}
全部评论

相关推荐

感觉今年拿到大厂实习offer的人很多,光是身边同学室友都是好几个offer。由此可见,秋招得有多卷
小浪_Coding:必须卷的起飞, 应该比25更卷一点, 25已经是哀声一片了, 26会更难一点, 现在还有`很多25未找到的
点赞 评论 收藏
分享
龙珠传说:nb,公务员解约不需要支付违约金吧
点赞 评论 收藏
分享
06-23 17:45
门头沟学院 Java
里面的项目啥的真的有用吗?&nbsp;这些人是割韭菜吗?
HellowordX:很简单,如果你有自己稳定的学习路线和获取知识的方式就没必要,如果你啥都不懂的小白或者里边有你感兴趣的知识,我觉得挺值,我也经常为知识付费,因为时间精力有限,很多东西我不可能自己重复造轮子
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务