算法
(KMP)
C++ 代码
//求两个序列的差值序列,然后用KMP
//k可以用set/unordered_set存储,l可以用multiset或者unordered_set,
//注意!!!m=1的时候没办法用KMP
#include<iostream>
#include<unordered_set>
#include<string>
#include<cmath>
using namespace std;
const int N =1e5+10,M = 1e5+10,inf = 0x3f3f3f3f;
int A[N],B[N],a[N],b[M],ne[N];
int T,n,m;
unordered_set<int> k;
int k_num,k_min,l_num,l_min,l_max;
void KMP()
{
k.clear();
k_min=l_min=inf;
l_max=l_num=0;
ne[0]=ne[1]=0;
int i = 2,j = 0;
for(i=2;i<m-1;i++){
while(j&&b[i-1]!=b[j]) j=ne[j];
if(b[i-1]==b[j]) j++;
ne[i]=j;
}
for(i=0,j=0;i<n-1;i++)
{
while(j&&a[i]!=b[j]) j = ne[j];
if(a[i]==b[j]) {j++;}
if(j==m-1){
k.insert(B[j-1]-A[i]);
k_min = min(k_min,abs(B[j-1]-A[i]));
l_num++;
l_min = min(l_min,i-j+2);
l_max = max(l_max,i-j+2);
j=ne[j-1];
i--;
}
}
k_num = k.size();
if(k_num==0) k_min=0;
if(l_num==0){
l_min=l_max=0;
}
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i = 0;i<n;i++) scanf("%d",&A[i]);
cin>>m;
for(int i = 0;i<m;i++) scanf("%d",&B[i]);
if(m!=1)
{
for(int i = 0;i<n-1;i++) a[i] = A[i+1]-A[i];
a[n-1]=inf;
for(int i = 0;i<m-1;i++) b[i] = B[i+1]-B[i];
b[m-1]=inf;
KMP();
cout<<k_num<<" "<<k_min<<" "<<l_num<<" "<<l_min<<" "<<l_max<<endl;
}
else
{
k.clear();
k_min=l_min=inf;
l_max=l_num=0;
for(int i = 0;i<n;i++)
{
k.insert(A[i]-B[0]);
k_min=min(k_min,abs(A[i]-B[0]));
l_min = min(l_min,i+1);
l_max = max(l_max,i+1);
}
k_num=k.size();
l_num = n;
cout<<k_num<<" "<<k_min<<" "<<l_num<<" "<<l_min<<" "<<l_max<<endl;
}
}
return 0;
}