博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 1711: Number Sequence
阅读量:5084 次
发布时间:2019-06-13

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

///@link http://acm.hdu.edu.cn/showproblem.php?pid=1711///@author Sycamore///@date 8/19/2017///@ref stanford-acm-master#include 
#include 
#include 
using namespace std; typedef vector
 VI;#define string VI#define length sizevoid buildPi(string& p, VI& pi){ pi = VI(p.length()); int k = -2; for (int i = 0; i < p.length(); i++) { while (k >= -1 && p[k + 1] != p[i]) k = (k == -1) ? -2 : pi[k]; pi[i] = ++k; }} int KMP(string& t, string& p){ VI pi; buildPi(p, pi); int k = -1; for (int i = 0; i < t.length(); i++) { while (k >= -1 && p[k + 1] != t[i]) k = (k == -1) ? -2 : pi[k]; k++; if (k == p.length() - 1) { // p matches t[i-m+1, ..., i] //cout << "matched at index " << i - k << ": "; return i - k; k = (k == -1) ? -2 : pi[k]; } } return -1;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int a_len, b_len; cin >> a_len >> b_len; VI a(a_len), b(b_len); for (auto &e : a)cin >> e; for (auto &e : b)cin >> e; int res = KMP(a, b); if (~res)cout << res + 1; else cout << -1; cout << '\n'; } return 0;}

 

转载于:https://www.cnblogs.com/zjnu/p/7395771.html

你可能感兴趣的文章
[转]jsbsim基础概念
查看>>
DIV和SPAN的区别
查看>>
第一次使用cnblogs
查看>>
C#语法糖之 session操作类 asp.net
查看>>
2015 Multi-University Training Contest 3
查看>>
使用Gitblit 在windows 上部署你的Git Server
查看>>
217. Contains Duplicate
查看>>
vue2.0 关于Vue实例的生命周期
查看>>
jenkins 更换主数据目录
查看>>
Silverlight中恼人的g.i.cs错误
查看>>
SQLite 数据库增删改查
查看>>
<s:iterator>的status
查看>>
C++入门--1.0输入输出
查看>>
让搭建在Github Pages上的Hexo博客可以被Google搜索到
查看>>
Introduction to 3D Game Programming with DirectX 12 学习笔记之 --- 第十四章:曲面细分阶段...
查看>>
在WPF控件上添加Windows窗口式调整大小行为
查看>>
背水一战 Windows 10 (36) - 控件(弹出类): ToolTip, Popup, PopupMenu
查看>>
教育类APP开发现新增长,多款APP该如何突围?
查看>>
打开3389
查看>>
React学习记录
查看>>