文档章节

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;    
}

© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 25
博文 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
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
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
mysql自动重启 有时重启后程序连接不上求教啊

160108 9:10:46 InnoDB: Started; log sequence number 0 6784661 160108 9:10:46 [Note] Event Scheduler: Loaded 0 events 160108 9:10:46 [Note] /usr/libexec/mysqld: ready for connect......

hphper
2016/01/18
337
0

没有更多内容

加载失败,请刷新页面

加载更多

20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
0
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
6
2
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
1
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
1
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部