首页 > 其他 > 详细

HDUNumber Sequence(KMP)

时间:2019-12-08 14:45:03      阅读:24      评论:0      收藏:0      [点我收藏+]

标签:sequence   传送门   def   代码   ont   while   

传送门

题目大意:b在a第一次出现的位置

题解:KMP

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000008
#define M 10009
using namespace std;

int T;

int a[N],b[M];

int nxt[M];

int lena,lenb;

void getnext()
{
    memset(nxt,0,sizeof(nxt));
    for(int i=2,j=0;i<=lenb;i++)
    {
        while(b[i]!=b[j+1]&&j) j=nxt[j];
        if(b[i]==b[j+1]) nxt[i]=++j;
    }
}

int KMP()
{
    getnext();
//    for(int i=0;i<=lenb;i++) cout<<i<<"---"<<nxt[i]<<endl;
    for(int i=1,k=0;i<=lena;i++)
    {
        for(;a[i]!=b[k+1]&&k;k=nxt[k]);
        if(a[i]==b[k+1])++k;
        if(k==lenb) return i-lenb+1;
    }
    return -1;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&lena,&lenb);
        for(int i=1;i<=lena;i++) scanf("%d",&a[i]);
        for(int i=1;i<=lenb;i++) scanf("%d",&b[i]);
        printf("%d\n",KMP()); 
    }
    return 0;
} 

 

HDUNumber Sequence(KMP)

标签:sequence   传送门   def   代码   ont   while   

原文:https://www.cnblogs.com/zzyh/p/12005385.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号