Number Sequence
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3450 Accepted Submission(s): 1555
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
题意:给两个数字序列a[1]......a[n],b[1]......b[m] 并且1 <= M <= 10000, 1 <= N <= 1000000,现在你的任务是找出b序列在a序列中存在的最小位置,和字符模式匹配一样
分析:如果用普通的字符模式匹配算法来解决此题会超时,显然应该用KMP算法
/**
**name:HDU1711
**result:Time Limit Exceeded
**author:Dev|il
**date:2011年9月9日 12:57
**/
#include <iostream>
using namespace std;
const int _N = 1000005;
const int _M = 10005;
int a[_N], b[_M];
int n, m;
int Index()
{
int i = 0, j = 0;
while(i < n && j < m)
{
if(a[i] == b[j])
{
++i;++j;
}else
{
i = i - j + 1;
j = 0;
}
}
if(j == m)
return i - m + 1;
return -1;
}
int main()
{
int t, i;
cin>>t;
while(t--)
{
cin>>n>>m;
for(i = 0; i < n; i++)
cin>>a[i];
for(i = 0; i < m; i++)
cin>>b[i];
cout<<Index()<<endl;
}
return 0;
}
以下是AC代码,KMP算法
/**
**name:HDU1711
**result:Accept
**author:Dev|il
**date:2011年9月9日 13:9
**/
#include <iostream>
using namespace std;
const int _N = 1000005;
const int _M = 10005;
int a[_N], b[_M], next[_M];
int n, m;
void getNext()
{
int i = 1, j = 0;
next[1] = 0;
while(i < m)
{
if(j == 0 || b[i] == b[j])
{
++i; ++j;
next[i] = j;
}else
j = next[j];
}
}
int Index()
{
getNext();
int i = 1, j = 1;
while(i <= n && j <= m)
{
if(j== 0 || a[i] == b[j])
{
++i;++j;
}
else
j = next[j];
}
if(j > m)
return i - m;
return -1;
}
int main()
{
int t, i;
cin>>t;
while(t--)
{
cin>>n>>m;
for(i = 1; i <= n; i++)
cin>>a[i];
for(i = 1; i <= m; i++)
cin>>b[i];
cout<<Index()<<endl;
}
return 0;
}
分享到:
相关推荐
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类