Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 22055 Accepted Submission(s): 9428
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
Source HDU 2007-Spring Programming Contest
/*"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例， － "A"的前缀和后缀都为空集，共有元素的长度为0； － "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0； － "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； － "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； － "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1； － "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2； － "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。*/ //next的含义就是这个字符串的前缀和后缀的最大的相同元素 //MAP的精髓所在 可以控制前移的位数 next的回溯十分重要 //理解KMP一定要弄懂next值所代表的含义 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <queue> #include <stack> using namespace std; const int MAXX=1000000+10; int a1[MAXX]; int a2[MAXX]; int nex[MAXX]; int n; int k; void Getnext(){ int i=0,j=-1; nex[0]=-1; while(i<k) { if(j==-1||a2[i]==a2[j]) nex[++i]=++j; else j=nex[j]; } } void KMP() { int num=0; int i=0; while(i<n){ if(num==-1||a1[i]==a2[num]){ num++;i++; if(num==k){ printf("%d\n",i-num+1); return ; } } else num=nex[num]; } printf("-1\n"); } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&a1[i]); for(int i=0;i<k;i++) scanf("%d",&a2[i]); Getnext(); KMP(); } return 0; }