首页 > 其他 > 详细

HDU 1711: Number Sequence

时间:2017-08-19 12:16:27      阅读:211      评论:0      收藏:0      [点我收藏+]


///@link http://acm.hdu.edu.cn/showproblem.php?pid=1711
///@author Sycamore
///@date 8/19/2017
///@ref stanford-acm-master
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
typedef vector<intVI;
#define string VI
#define length size
void buildPi(stringpVIpi)
{
	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(stringtstringp)
{
	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;
}

 

HDU 1711: Number Sequence

原文:http://www.cnblogs.com/zjnu/p/7395771.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!