题意:
给你T串和模板P串,输出P第一次出现的位置.
分析:
简单KMP,直接用模板.
#include<bits/stdc++.h>using namespace std;const int maxn = 1e7;
int T[maxn],P[maxn],f[maxn],f2[maxn];
int n,m;void getfail()
{f[0] = f[1] =0;f2[0] = f2[1] = 0;for(int i=1;i<m;i++){int j=f2[i];while(j && P[i]!=P[j])j=f2[j];f2[i+1]=f[i+1]=P[i]==P[j]?j+1:0;if(f[i+1]==j+1 && P[i+1]==P[j+1])f[i+1]=f[j+1];//这里优化不优化都行}
}
int find()
{getfail();int j=0;for(int i=0;i<n;i++){while(j && T[i]!=P[j])j=f2[j];if(T[i]==P[j])j++;if(j==m)return i-m+1+1;//下标从1开始}return -1;
}int main()
{int k;cin>>k;while(k--){cin>>n>>m;for(int i=0;i<n;i++)scanf("%d",T+i);T[n]=1e8;for(int i=0;i<m;i++)scanf("%d",P+i);P[m]=1e8;int ans=find();cout<<ans<<endl;}
}