【杭电oj1711】Number Sequence

待我称王封你为后i 2022-09-25 06:28 161阅读 0赞

# Number Sequence #

**Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 22047 Accepted Submission(s): 9420**

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][]

Recommend

lcy | We have carefully selected several similar problems for you: [1358][] [3336][] [1686][] [3746][] [1251][]

经过此题（虽是模板题）发现我这菜鸟还是对KMP算法没有深入的理解，掌握不好，处处出错。看来要继续深层次理解KMP算法啊。。。。。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N = 1e6+10;
    const int M = 1e4+5;
    int p[N],s[N];
    int ans,n,m;
    void getNext(int *s,int *next) {
    	int j,k;
    	next[0]=-1;
    	j=0,k=-1;
    	while(j<m-1) {
    		if(k==-1||s[j]==s[k]) {
    			j++;
    			k++;
    			//	if(s[j]!=s[k])
    			next[j]=k;
    			//	else
    			//		next[j]=next[j];
    		} else
    			k=next[k];
    	}
    }
    int KMPMatch(int *p,int *s) {
    	int i,j;
    	int next[M];
    	i=0,j=0;
    	getNext(s,next);  //忘加了
    //	printf("--\n");
    	while(i<n) {
    		if(j==-1||p[i]==s[j]) {
    			j++;
    			i++;
    			//		printf("---\n");
    		} else {
    			j=next[j];
    		}
    		if(j==m)
    			return i-m+1;
    	}
    	return -1;
    }
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		scanf("%d%d",&n,&m);
    		for(int i=0; i<n; i++) {
    			scanf("%d",&p[i]);
    		}
    		for(int j=0; j<m; j++) {
    			scanf("%d",&s[j]);
    		}
    		ans=KMPMatch(p,s);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_showproblem.php_pid_1711]

[HDU 2007-Spring Programming Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU+2007-Spring+Programming+Contest&source=1&searchmode=source
[1358]: http://acm.hdu.edu.cn/showproblem.php?pid=1358
[3336]: http://acm.hdu.edu.cn/showproblem.php?pid=3336
[1686]: http://acm.hdu.edu.cn/showproblem.php?pid=1686
[3746]: http://acm.hdu.edu.cn/showproblem.php?pid=3746
[1251]: http://acm.hdu.edu.cn/showproblem.php?pid=1251
[http_acm.hdu.edu.cn_showproblem.php_pid_1711]: http://acm.hdu.edu.cn/showproblem.php?pid=1711