hdoj1711（kmp算法）

题目链接：https://www.cnblogs.com/kuangbin/archive/2012/08/14/2638803.html

题意：给定两个数组a、b，在数组a中查找b，求第一次出现的下标，若没有则输出-1。

思路：kmp算法的应用.

AC代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=1e6+5;
const int maxm=1e4+5;
int T,n,m;
int nex[maxm],a[maxn],b[maxm];

void get_next(){
    int j=nex[0]=-1;
    for(int i=1;i<m;++i){
        while(j>-1&&b[i]!=b[j+1]) j=nex[j];
        if(b[i]==b[j+1]) ++j;
        nex[i]=j;
    }
}

int kmp(){
    int j=-1;
    for(int i=0;i<n;++i){
        while(j>-1&&a[i]!=b[j+1]) j=nex[j];
        if(a[i]==b[j+1]) ++j;
        if(j==m-1) return i-m+1+1;
    }
    return -1;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i)
            scanf("%d",&a[i]);
        for(int i=0;i<m;++i)
            scanf("%d",&b[i]);
        get_next();
        printf("%d\n",kmp());
    }
    return 0;
}