hdoj_1711_Number Sequence
hdoj_1711_Number Sequence
電泡泡 发表于5年前
hdoj_1711_Number Sequence
  • 发表于 5年前
  • 阅读 15
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

#include <stdio.h>
#include <iostream>
using namespace std;

int s[1000010], p[10010];
int next[10010];
int m, n, ans, t;

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

int 
main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
    cin>>t;
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; i++){
            scanf("%d", &s[i]);
        }    
        for(int i=1; i<=m; i++){
            scanf("%d", &p[i]); 
        }
        getnext();
        ans=kmp();
        cout<<ans<<endl;
    }
    return 0;    
}
共有 人打赏支持
粉丝 25
博文 181
码字总数 69717
×
電泡泡
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: