数据结构之KMP算法---hdu---Number Sequence
发布日期:2022-02-02 02:58:08
浏览次数:28
分类:技术文章
本文共 1359 字,大约阅读时间需要 4 分钟。
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
213 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 1 313 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 2 1
Sample Output
6-1代码实现: #include#include using namespace std;int next[10005];int a[1000005],b[10005];void getNext(int *b,int m,int n){ int i=0,j=-1; next[0]=-1; while(i >t; while(t--) { cin>>m>>n; for(int i=0;i >a[i]; } for(int j=0;j >b[j]; } getNext(b,m,n); int i=0,j=0,flag=0; while(i
转载地址:https://blog.csdn.net/u010368749/article/details/19328879 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月13日 20时54分54秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【Java面试题四】sql面试题(1)
2019-04-26
【Java面试题五】sql面试题(2)
2019-04-26
【Java面试题六】多线程篇
2019-04-26
【Java面试题七】Java泛型篇
2019-04-26
【Java面试题八】Java算法优化篇
2019-04-26
JDBC与DAO篇--01 JDBC原理、JDBC基础编程
2019-04-26
【Java面试题九】算法篇
2019-04-26
架构设计与分层
2019-04-26
【01】Java面试----基础方面的陷阱
2019-04-26
排序算法整合
2019-04-26
Java程序员常见笔试题分析
2019-04-26
Java笔试题
2019-04-26
Spring Boot快速入门---(一)spring boot的创建及几种启动方式
2019-04-26
【物联网实训项目】------(一)家庭智慧安防系统之前期项目工作准备
2019-04-26
【物联网实训项目】------(二)家庭智慧安防系统之定时监控
2019-04-26
【物联网实训项目】------(三)家庭智慧安防系统之实时监控
2019-04-26