文档章节

hdoj_1711_Number Sequence

電泡泡
 電泡泡
发布于 2013/04/24 17:41
字数 142
阅读 34
收藏 0
#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;    
}

© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 24
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
区间DP小结(附经典例题)

——这篇文章主要想总结下区间DP的经典题目,同时给自己复习巩固这方面知识点。 区间DP 一、定义 区间DP,顾名思义是在区间上DP,它的主要思想就是先在小区间进行DP得到最优解,然后再利用小...

my_sunshine26
2017/08/13
0
0
反素数求解及相关题目

反素数 定义:对于任何正整数n,其约数个数记为f(n),例如f(6)=4;如果存在一个正整数n满足:对于任意的正整数x(0

my_sunshine26
2017/05/26
0
0
TCP/IP Troubleshooting

TCP/IP Troubleshooting: How to detect issues at the transport layer. Just a reminder: TCP/IP is both a protocol suite (a set of communications protocols used on the Internet and......

robin-yao
2015/11/14
0
0
Project Honolulu Technical Preview 1711 Build 0100

Project Honolulu Technical Preview 1711 Build 0100 gOxiA=苏繁=SuFan's Blog2017-11-203 阅读 WindowsServer Project Honolulu Technical Preview 1711 Build 01003 忍了好久终于可以发布......

gOxiA=苏繁=SuFan's Blog
2017/11/20
0
0
hdoj 1020 Encoding

EncodingTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 52209 Accepted Submission(s): 23212 include int main(){//freopen("t......

dear_jia
04/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux脚本中父shell与子shell 执行的几种方式

本文主要介绍以下几个命令的区别: shell subshell source $ (commond) `commond` Linux执行Scripts有两种方式,主要区别在于是否建立subshell 1. source filename or . filename 不创建sub...

问题终结者
14分钟前
1
0
安装jdk和Tomcat

12月12日任务 16.1 Tomcat介绍 16.2 安装jdk 16.3 安装Tomcat Tomcat介绍 Tomcat是apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由apache、Sun和其他一些...

robertt15
15分钟前
3
0
Beetl 免费视频

来自 https://my.oschina.net/gking?q=Beetl ,Beetl终于有人录制视频了 项目git地址:https://gitee.com/gavink/beetl-blog 视频地址:下载下来会更清晰,视频比较长,可使用倍速看 百度网盘...

闲大赋
27分钟前
0
0
isEmpty和null的区别

isEmpty和null的区别: 1.一个是对象为空(IsNull),一个是值为空(IsEmpty) 2.IsNull指任务类型变量是否为空包括对象类型的变量。 IsNull函数: 功能:返回Boolean的值,指明表达是否不包...

DemonsI
54分钟前
3
0
Centos7 安装mysql与php

https://blog.csdn.net/qq_36431213/article/details/79576025 官网下载安装mysql-server 依次使用下面三个命令安装 wget http://dev.mysql.com/get/mysql-community-release-el7-5.noarch.r......

Yao--靠自己
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部