KMP入门题

偏执的太偏执、 2024-01-16 00:42 24阅读 0赞

## Number Sequence ##

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

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 ][HDU 2007-Spring Programming Contest]

Recommend

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

难点：注意数的范围，用字符数组不行，只能用int，而且，用scanf输入，987ms，用cin超时。

模板题：

#include<iostream>
    #include<cstdio>
    #include<string.h>
    using namespace std;
    #define range 1000000
    int str[range+5];
    int ptr[10005];
    void cal_next(int p_len,int *next)
    {
    	int i,j,k=-1;
    	next[0]=-1;
    	for(i=1;i<p_len;i++)
    	{
    		while(k>=0&&ptr[k+1]!=ptr[i])
    		k=next[k];
    		if(ptr[k+1]==ptr[i])
    		k++;
    		next[i]=k;
    	}
    }
    int KMP(int s_len,int p_len)
    {
    	int *next=new int[p_len];
    	cal_next(p_len,next);
    	
    	
    	int k=-1;
    	for(int i=0;i<s_len;i++)
    	{
    		while(k>=0&&ptr[k+1]!=str[i])
    		k=next[k];
    		if(ptr[k+1]==str[i])
    		k++;
    		if(k==p_len-1)
    		{
    			cout<<i-p_len+1+1<<endl;
    			return 1;
    		}
    	}
    	cout<<-1<<endl;
    	return 0;
    }
    int main()
    {
    	int n,s_len,p_len;
    	cin>>n;
    	while(n--)
    	{
    		
    		cin>>s_len>>p_len;
    		for(int i=0;i<s_len;i++)
    		scanf("%d",&str[i]);
    		for(int i=0;i<p_len;i++)
    		scanf("%d",&ptr[i]);
    		KMP(s_len,p_len);
    		
    	}
    	return 0;
    }

[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