A - Number Sequence

Given two sequences of numbers : a11, a22, ...... , aNN, and b11, b22, ...... , bMM(1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make aKK = b11, aK+1K+1 = b22, ...... , aK+M−1K+M−1 = bMM. If there are more than one K exist, output the smallest one.

InputThe 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 a11, a22, ...... , aNN. The third line contains M integers which indicate b11, b22, ...... , bMM. All integers are in the range of −1000000,1000000−1000000,1000000.
OutputFor 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

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

using namespace std;

#define MAXN 1000001

typedef long long LL;

/*

KMP  查找子串首次出现的位置

*/

int s[MAXN],t[MAXN],Next[MAXN];

void kmp_pre(int m)

{

    int j,k;

    j=;k=-;Next[]=-;

    while(j<m)

    {

        if(k==-||t[j]==t[k])

            Next[++j] = ++k;

        else

            k = Next[k];

    }

}

int KMP(int n,int m)

{

    int i,j,ans;

    i=j=ans=;

    kmp_pre(m);

    if(n==&&m==)

        return (s[]==t[])?:-;

    for(i=;i<n;i++)

    {

        while(j>&&s[i]!=t[j])

            j = Next[j];

        if(s[i]==t[j])

            j++;

        if(j>=m)

        {

            if(i-m+>)

                return i-m+;

            else

                return -;

        }

    }

    return -;

}

int main()

{

    int T,n,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=;i<n;i++)

            scanf("%d",&s[i]);

        for(int i=;i<m;i++)

            scanf("%d",&t[i]);

        printf("%d\n",KMP(n,m));

    }

}

巴特西

A - Number Sequence

最新文章

热门文章