说实话，这题看懂题意后秒出思路，和顺波说了一下是KMP，后来过了一会确定了思路他开始写我中途接了个电话，回来kaungbin模板一板子上去直接A了。
题意：有两座城堡，每座城堡有一定的形状分别由高度区分。求第一座城堡中有多少个区间的形状和第二座城堡相似。连续一段区间高度可以任意变，但他们的相对位置是不变的。
思路：基于一段连续区间无论怎么变他们的相对位置不会变，所以分别将两个序列相邻的元素作差，一段区间的相对位置不会变，所以正好可以用差值去匹配。所以KMP模式匹配很好解决了这个问题，注意数组用int 型。
const int N=2e5+7;
int len1,len2,a[N],b[N],f[N],p[N];
void kmp_pre(int *x,int m,int *next)//以下感谢kuangbin神主提供的模板。
{
int i,j;
j=next[0]=-1;
i=0;
while(i<m)
{
while(-1!=j&&x[i]!=x[j]) j=next[j];
next[++i]=++j;
}
}
void prekmp(int *x,int m,int *kmpnext)
{
int i,j=-1;
kmpnext[0]=-1;
i=0;
while(i<m)
{
while(-1!=j&&x[i]!=x[j]) j=kmpnext[j];
if(x[++i]==x[++j]) kmpnext[i]=kmpnext[j];
else kmpnext[i]=j;
}
}
int next[N];
int kmp_count(int *x,int m,int *y,int n)
{
int i,j,ans=0;
kmp_pre(x,m,next);
i=j=0;
while(i<n)
{
while(-1!=j&&y[i]!=x[j]) j=next[j];
i++,j++;
if(j>=m)
{
ans++;
j=next[j];
}
}
return ans;
}
int main()
{
int w,n;
while(~scanf("%d%d",&w,&n))
{
len1=0,len2=0;
for(int i=0;i<w;i++)
{
scanf("%d",&a[i]);
if(i) f[len1++]=a[i]-a[i-1];
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
if(i) p[len2++]=b[i]-b[i-1];
}
if(n==1)
{
printf("%d\n",w);
continue;
}
int ans=kmp_count(p,len2,f,len1);
printf("%d\n",ans);
}
return 0;
}
正确快速读懂题意很重要，思路清晰想到了就是模板题。