A - Number Sequence 哈希算法（例题）

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.

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 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].
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
哈希算法的模板题，题目数据没有当 n < m 的情况

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int N=1E6+;

const int M=1E4+;

const int base =;

const int mod=1e9+;

typedef unsigned long long ll;

ll a[N],b[M];

ll ha[N],p[N];

ll gethash(ll x,ll y){

    return (ha[y]%mod-(ha[x-]%mod*p[y-x+]%mod)%mod+mod)%mod;

}

int main(){

    int t;

//    cin>>t;

    scanf("%d",&t);

    while(t--){

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

        ll n,m;

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

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

            scanf("%lld",&a[i]);

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

            scanf("%lld",&b[i]);

        p[]=;

        if(n>=m){

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

                ha[i]=((ha[i-]%mod*base)%mod+a[i])%mod;

                p[i]=(p[i-]%mod*base)%mod;

            }

            ll ans=;

            for(int i=;i<=m;i++) ans=(ans%mod*base+b[i])%mod;

            int pos=;

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

                if(gethash(i-m+,i)==ans){

                    pos=i-m+;

                    break;

                }

            }

            if(pos==) pos=-;

            printf("%d\n",pos);

        }

//        else {

//            for(int i=1;i<=m;i++){

//                ha[i]=((ha[i-1]%mod*base)%mod+b[i])%mod;

//                p[i]=(p[i-1]%mod*base)%mod;

//            }

//            ll ans=0;

//            for(int i=1;i<=n;i++) ans=(ans%mod*base+a[i])%mod;

//            int pos=0;

//            for(int i=n;i<=m;i++){

//                if(gethash(i-n+1,i)==ans){

//                    pos=i-n+1;

//                    break;

//                }

//            }

//            if(pos==0) pos=-1;

//            printf("%d\n",pos);

//        }

    }

    return ;

}

巴特西

A - Number Sequence 哈希算法（例题）

最新文章

热门文章