HDU - 1711 Number Sequence （KMP）

ゞ浴缸里的玫瑰 2022-05-19 07:50 218阅读 0赞

#                                   Number Sequence #

### 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 ###

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 ###

\-1

**题意描述：**

在序列A中找到序列B的位置，若不包含序列B输出-1.

**解题思路：**

完全kmp算法模板题，先求出序列B的next\[\]数组，再利用KMP算法求出位置定义一个flag若不包含输出-1.

#include<stdio.h>
    #include<string.h>
    int a[1000005],b[10005];
    int next[10005],n,m;
    void get_next(int b[],int m)
    {
    	int i,j;
    	j=0;
    	i=1;
    	next[0]=0;
    	while(i<m)
    	{
    		
    		if(b[i]==b[j])
    		{
    			next[i]=j+1;
    			i++;
    			j++;
    		}
    		if(j==0&&b[i]!=b[j])
    		{
    			next[i]=0;
    			i++;
    		}
    		if(j>0&&b[i]!=b[j])
    			j=next[j-1];
    	}
    }
    int main()
    {
    	
    	int i,j,num,t,flag;
    	while(scanf("%d\n",&t)!=EOF)
    	{
    		while(t--)
    		{
    			scanf("%d%d",&n,&m);
    			for(i=0;i<n;i++)
    				scanf("%d",&a[i]);
    			for(j=0;j<m;j++)
    				scanf("%d",&b[j]);
    			get_next(b,m);
    			i=0;
    			j=0;
    			flag=0;
    			while(i<=n)
    			{
    				if(a[i]==b[j])
    				{
    					j++;
    					if(j==m)
    					{
    						flag=1;
    						num=i-m+2;
    						break;
    					}
    					i++;
    				}
    				if(j==0&&a[i]!=b[j])
    					i++;
    				if(j>0&&a[i]!=b[j])
    					j=next[j-1];
    			}
    			if(flag==1)
    				printf("%d\n",num);
    			else
    				printf("-1\n");
    		}
    	}
    	return 0;
    }