文档章节

hdoj_1711_Number Sequence

電泡泡
 電泡泡
发布于 2013/04/24 17:41
字数 142
阅读 34
收藏 0
点赞 0
评论 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
博文 181
码字总数 69717
作品 0
衡阳
区间DP小结(附经典例题)

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

my_sunshine26 ⋅ 2017/08/13 ⋅ 0

反素数求解及相关题目

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

my_sunshine26 ⋅ 2017/05/26 ⋅ 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

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

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 ⋅ 0

MySQL5.7 GTID与传统快速切换

当前场景: 某些业务场景还未开启GTID服务组,在最新版本中,BINLOG组提交也基于GTID方式,因此如何检测是否符合开启GTID条件,在线切换使用GTID,以及如何快速回滚: gtidmode参数新选项:M...

DBAspace ⋅ 2017/11/17 ⋅ 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

POJ 1007 -- DNA Sorting

DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 94974 Accepted: 38197 Description One measure of unsortedness'' in a sequence is the number of pairs of en......

圣洁之子 ⋅ 2016/05/27 ⋅ 0

POJ1007·DNA Sorting

一道水题,算法也没用多么复杂的,但在G++环境下提交成功,C++会报编译不过的错误。 Description One measure of unsortedness'' in a sequence is the number of pairs of entries that are...

OldPanda ⋅ 2012/06/01 ⋅ 4

HDOJ 1009 FatMouse' Trade

FatMouse' TradeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 81301 Accepted Submission(s): 28137 Problem Description FatM......

Dear_Jia ⋅ 2017/09/30 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

LVM

LVM: 硬盘划分分区成物理卷->物理卷组成卷组->卷组划分逻辑分区。 1.磁盘分区: fdisk /dev/sdb 划分几个主分区 输入t更改每个分区类型为8e(LVM) 使用partprobe生成分区的文件:如/dev/sd...

ZHENG-JY ⋅ 39分钟前 ⋅ 0

彻底删除Microsoft Office的方法

参照此链接彻底删除Office https://support.office.com/zh-cn/article/%e4%bb%8e-pc-%e5%8d%b8%e8%bd%bd-office-9dd49b83-264a-477a-8fcc-2fdf5dbf61d8?ui=zh-CN&rs=zh-CN&ad=CN......

Kampfer ⋅ 54分钟前 ⋅ 0

大盘与个股之间关系

大盘走多:积极出手 顺势加码 大盘走空: 少量出手 退场观望 大盘做头:逆势减码 少量操作 大盘做底 : 小量建仓 小量试单

guozenhua ⋅ 56分钟前 ⋅ 0

Day16 LVM(逻辑卷管理)与磁盘故障小案例

lvm详解 简述 LVM的产生是因为传统的分区一旦分区好后就无法在线扩充空间,也存在一些工具能实现在线扩充空间但是还是会面临数据损坏的风险;传统的分区当分区空间不足时,一般的解决办法是再...

杉下 ⋅ 今天 ⋅ 0

rsync实现多台linux服务器的文件同步

一、首先安装rsync,怎样安装都行,rpm,yum,还是你用源码安装都可以。因为我用的是阿里云的ESC,yum install rsync就ok了。 二、配置rsync服务 1.先建立个同步数据的帐号 123 groupadd r...

在下头真的很硬 ⋅ 今天 ⋅ 0

前端基础(三):函数

字数:1685 阅读时间:5分钟 函数定义 在最新的ES规范中,声明函数有4中方法: -函数声明 -函数表达式 -构造函数Function -生成器函数 1.函数声明 语法: function name([param[, param2 [....

老司机带你撸代码 ⋅ 今天 ⋅ 0

Java虚拟机的Heap监狱

在Java虚拟机中,我是一个位高权重的大管家,他们都很怕我,尤其是那些Java 对象,我把他们圈到一个叫做Heap的“监狱”里,严格管理,生杀大权尽在掌握。 中国人把Stack翻译成“栈”,把Hea...

java高级架构牛人 ⋅ 今天 ⋅ 0

Spring MVC基本概念

只写Controller

颖伙虫 ⋅ 今天 ⋅ 0

微软重金收购GitHub的背后逻辑原来是这样的

全球最大的开发者社区GitHub网站花落谁家的问题已经敲定,微软最终以75亿美元迎娶了这位在外界看来无比“神秘”的小家碧玉。尽管此事已过去一些时日,但整个开发者世界,包括全球各地的开源社...

linux-tao ⋅ 今天 ⋅ 0

磁盘管理—逻辑卷lvm

4.10-4.12 lvm 操作流程: 磁盘分区-->创建物理卷-->划分为卷组-->划分成逻辑卷-->格式化、挂载-->扩容。 磁盘分区 注: 创建分区时需要更改其文件类型为lvm(代码8e) 分区 3 已设置为 Linu...

弓正 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部