HDU 1711 Number Sequence（数列）
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
|
【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. |
给定两串数组 : a[1], a[2], ...... , a[N], 和 b[1], b[2], ...... , b[M] (1 <= N <= 1000000, 1 <= M <= 10000)。你的任务是找到一个数字K使得a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]。如果存在多个K, 输出最小的那个。 |
|
【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]. |
输入的第一行是一个数字T 表示测试用例的数量。每个测试用例有三行。 第一行神两个数N和M (1 <= M <= 10000, 1 <= N <= 1000000)。 第二行有N个整数a[1], a[2], ...... , a[N]。 第三行有M个整数b[1], b[2], ...... , b[M]。 所有整数的范围都在 [-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. |
对于每个测试用例，输出一行上述K值。如果K不存在，则输出-1. |
|
【Sample Input - 输入样例】 |
【Sample Output - 输出样例】 |
|
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 |
6 -1 |
【题解】
KMP可解，初次匹配成功的时候结束即可。
【代码 C++】
#include <cstdio>
int a[], b[];
int aLen, bLen, next[] = { - };
void setNext_b(){
int i = , j = -;
while (i < bLen){
if (j == - || b[i] == b[j]) next[++i] = ++j;
else j = next[j];
}
}
int fid(){
int i = , j = ;
while (i < aLen){
if (j == - || a[i] == b[j]) ++i, ++j;
else j = next[j];
if (j == bLen) return i - j + ;
}
return -;
}
int main(){
int i, t;
scanf("%d", &t);
while (t--){
scanf("%d%d", &aLen, &bLen);
for (i = ; i < aLen; ++i) scanf("%d", &a[i]);
for (i = ; i < bLen; ++i) scanf("%d", &b[i]);
setNext_b();
printf("%d\n", fid());
}
return ;
}