(KMP 模板)Number Sequence -- Hdu -- 1711
2024-10-21 11:41:30
http://acm.hdu.edu.cn/showproblem.php?pid=1711
Number Sequence
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16080 Accepted Submission(s): 7100
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
Source
Next里面存的是前缀和后缀的最大相似度
Next[i] 代表的是前 i 个数的最大匹配
#include<stdio.h>
#include<string.h>
#include<stdlib.h> #define N 1000007 int M[N], S[N], Next[N]; void FindNext(int Slen)
{
int i=, j=-;
Next[] = -; while(i<Slen)
{
if(j==- || S[i]==S[j])
Next[++i] = ++j;
else
j = Next[j];
}
} int KMP(int Mlen, int Slen)
{
int i=, j=; FindNext(Slen); while(i<Mlen)
{
while(j==- || (M[i]==S[j] && i<Mlen && j<Slen))
i++, j++;
if(j==Slen)
return i-Slen+; j = Next[j];
}
return -;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n, m, i; scanf("%d%d", &n, &m); for(i=; i<n; i++)
scanf("%d", &M[i]);
for(i=; i<m; i++)
scanf("%d", &S[i]); printf("%d\n", KMP(n, m));
}
return ;
}
最新文章
- 学习zepto.js(对象方法)[4]
- iOS如何跳到系统设置里的各种设置界面
- Http Status 参考
- C primer plus 练习题 第七章
- Struts2中的ActionContext、OGNL及EL的使用
- UVa 10420 List of Conquests
- SQL索引优化
- mount nfs的可选参数
- java中两种类型变量
- 关于ListView中convertView的缓存个数的探究
- Merge INTO的用法参考
- 深入理解 JavaScript(二)
- MySQL数据库主从复制实践
- python_web----------数据可视化从0到1的过程
- Java Web 禁用Cookie对Session的影响
- 2018-软工机试-C-和你在一起
- Dubbo-Admin 2.6.0使用
- ****** 二十八 ******、软设笔记【数据库】-分布式数据库、特点、数据存储、DBMS组成
- require.ensure的用法;异步加载-代码分割;
- diyiti.cpp
热门文章
- 多个jsp页面共享Java bean
- ArcGIS案例学习笔记1_1
- Pandas缺失数据处理
- 关于sql 增删改
- python中的__name__==&#39;__main__&#39;如何简单理解(一)
- express + mongodb 搭建一个简易网站(二)
- 带图标的input
- 51. N-Queens (Array; Back-Track, Bit)
- SQL日期和时间函数
- 使用百度网盘配置私有Git服务