题目大意:

还是kmp魔板题,给你两串数,从一串中找出另一串,要是存在多个,就输出最先找到的位置。

代码:

#include<iostream>
#include<math.h>
#include<stdio.h>

using namespace std;
int a[1000500];
int c[10050];
int m,n;
int my_next[10050];

void get_my_next()
{
    int i=0,k=-1;
    my_next[0]=-1;
    while(i<m)
    {
        if(k!=-1&&c[i]!=c[k])
        {
            k=my_next[k];
            continue;
        }
        i++;k++;
        if(c[i]==c[k])my_next[i]=my_next[k];
        else my_next[i]=k;
    }
}

int my_kmp()
{
    int i=0,j=0;
    while(i<n)
    {
        if(j==-1||a[i]==c[j])
        {
            i++;j++;
        }
        else
        {
            j=my_next[j];
        }
        if(j==m)
        {
            return i-m+1;
        }
    }
    return -1;
}

int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        scanf("%d",&n);
        scanf("%d",&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d",&c[i]);
        }
        get_my_next();
        cout<<my_kmp()<<endl;
    }
}