HDU 1711 Number Sequence //简单kmp

忘是亡心i 2022-08-23 11:54 157阅读 0赞

# Number Sequence #

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

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][] [3746][] [1251][] [2222][]

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

[HDU 2007-Spring Programming Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU%202007-Spring%20Programming%20Contest&source=1&searchmode=source
[1358]: http://acm.hdu.edu.cn/showproblem.php?pid=1358
[3336]: http://acm.hdu.edu.cn/showproblem.php?pid=3336
[3746]: http://acm.hdu.edu.cn/showproblem.php?pid=3746
[1251]: http://acm.hdu.edu.cn/showproblem.php?pid=1251
[2222]: http://acm.hdu.edu.cn/showproblem.php?pid=2222