HDU - 1711 Number Sequence (KMP模板)
发布日期:2021-06-21 09:00:12 浏览次数:2 分类:技术文章

本文共 1657 字,大约阅读时间需要 5 分钟。

题目:

Problem Description

Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample Input

2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1

Sample Output

6 -1

大意:

有a,b两个整数数组,在a数组里面找到第一个匹配b数组的位置。

思路:

KMP模板题

代码:

/*by kzl*/#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;const int maxx = 1e6+500;const int INF = 0x3f3f3f3f;typedef long long LL;int n,m,t;int a[maxx],b[maxx];int fail[maxx];void getfail(int len){ int i=0,j=-1; fail[0] = -1; while(i!=len){ if(j==-1||b[i]==b[j]){ fail[++i] = ++j; } else{ j = fail[j]; } }}int getindex(int len,int len1){ int i=0,j=0; while(i!=len){ if(j==-1||a[i]==b[j]){ i++;j++; if(j==len1)return i-len1+1; } else { j = fail[j]; } } return -1;}int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i

 

转载地址:https://blog.csdn.net/lwgkzl/article/details/82534682 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:CSU - 1581 Clock Pictures(简单KMP)
下一篇:HDU - 2717 Catch That Cow (简单BFS)

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月07日 15时52分24秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python多线程实现kmeans,3种方式实现python多线程并发处理 2019-04-21
matlab 变量不存在,matlab程序运行时提示变量未定义 2019-04-21
php编码函数 base58,1. Base58可逆加密 2019-04-21
oracle 在需要下列之一,Oracle存储过程中PLS-00103:出现符号“/”在需要下列之一时:(... 2019-04-21
oracle10g dblink优化,Oracle10g通过dblink访问数据异常 2019-04-21
linux安装时的iso文件,直接用ISO文件在linux上安装新系统 2019-04-21
linux修改文件权限为所有人都可以访问,Linux 笔记分享八:文件权限的设定 2019-04-21
linux中卸载ambri-servle,Kerberos 命令使用 2019-04-21
linux二进制反编译,Xori:一款来自BlackHat 2018的二进制反汇编和静态分析工具 2019-04-21
linux两台主机添加信任,Linux两台机器间添加信任,实现不用密码问,互传文件... 2019-04-21
linux 自动获取ssl证书,linux生成自验证ssl证书的具体命令和步骤 2019-04-21
linux基础命令20个,20-linux中基础命令 2019-04-21
重置网络配置 android,重置Android移动网络信号? 2019-04-21
java约瑟夫环pta上_cdoj525-猴子选大王 (约瑟夫环) 2019-04-21
java++记录+运行_记录java+testng运行selenium(三)---xml、ini、excel、日志等配置 2019-04-21
mysql居左查询abcd_MySql速查手册 2019-04-21
loadrunner 错误: 无法找到 java.exe_LoadRunner错误及解决方法总结 2019-04-21
Java小魔女芭芭拉_沉迷蘑菇不可自拔,黏土人《小魔女学园》苏西·曼芭芭拉 图赏... 2019-04-21
php+mysql记事本_一个简单记事本php操作mysql辅助类创建 2019-04-21
300小时成为java程序员_直击面试现场: Java程序员3轮6小时面试, 成功拿到阿里offer!... 2019-04-21