HDU 1711 Number Sequence【字符串】
发布日期:2021-07-01 02:50:20
浏览次数:2
分类:技术文章
本文共 2270 字,大约阅读时间需要 7 分钟。
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
题意:找出 b
数组在 a
数组中出现的第一个位置。
思路:KMP板子题。代码如下:
#includeusing namespace std;const int smaxn = 1000000 + 10, pmaxn = 10000 + 10;int s[smaxn], p[pmaxn];int nextArr[pmaxn];int cases, n, m;namespace kmp1 { void getNext() { nextArr[0] = nextArr[1] = 0; for (int i = 1; i < m; ++i) { int j = nextArr[i]; while (j && p[i] != p[j]) j = nextArr[j]; nextArr[i + 1] = (p[i] == p[j] ? j + 1 : 0); } } int kmp() { if (n < m) return -1; getNext(); int j = 0; for (int i = 0; i < n; ++i) { while (j && s[i] != p[j]) j = nextArr[j]; if (s[i] == p[j]) ++j; if (j >= m) return i + 2 - j; } return -1; }}namespace kmp2 { void getNext() { nextArr[0] = -1, nextArr[1] = 0; int pos = 2, cn = 0; while (pos <= m) { if (p[pos - 1] == p[cn]) nextArr[pos++] = ++cn; else if (cn > 0) cn = nextArr[cn]; else nextArr[pos++] = cn; } } int kmp() { if (n < m) return -1; getNext(); int i = 0, j = 0; while (i < n && j < m) { if (s[i] == p[j]) ++i, ++j; else if (nextArr[j] != -1) j = nextArr[j]; else ++i; if (j >= m) return i + 1 - j; } return -1; }}int main() { scanf("%d", &cases); while (cases--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", &s[i]); for (int i = 0; i < m; ++i) scanf("%d", &p[i]); printf("%d\n", kmp1::kmp()); } return 0;}
提交结果如下:
转载地址:https://memcpy0.blog.csdn.net/article/details/108249422 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月16日 17时37分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【语言-c#】C# 超级整数计算
2019-05-02
【软件-Doxgen】工具:程序代码生成xml文档(doxgen)
2019-05-02
【语言-c#】C# 注释详细介绍说明
2019-05-02
MySQL 内存模型
2019-05-02
express 解析post方式下的json参数
2019-05-02
node.js 实现一个简单的登录拦截器
2019-05-02
c++抽象类、纯虚函数以及巧用纯虚析构函数实现接口类【转】
2019-05-02
Caffe 安装错误记录及解决办法【转】
2019-05-02
Android用类继承Application的全局变量使用注意
2019-05-02
排序算法之冒泡排序
2019-05-02
算法排序之桶排序
2019-05-02
lambda表达式初探
2019-05-02
C++ Template类模板的特化(3.3节, 3.4节)
2019-05-02
第05章 函数
2019-05-02
第08章 输入和输出
2019-05-02
QT中文乱码的解
2019-05-02
netsh用法
2019-05-02
网上Qt多线程同步的一种普遍误识
2019-05-02