链接：http://vjudge.net/contest/143819#problem/D

CodeForces471D

题意：你建造了一堵墙，这堵墙是由n个塔组成的，每个塔相互连接，且各自有一个高度，你给你自己的墙起了一个名字，叫大象。
猪也建造了一堵墙。问你最多能从猪建的墙中找到几个大象。你可以将你自己的墙中的塔向上提升，或者下降，可以降到地下。

解析：开始题意没有理解。不是你对墙做任意的行为，而是你可以把你的墙的基底的高度改变。此题可以抽象成用猪的墙取匹配大象，问最多能匹配几次。

而实际上单个墙的高度对匹配无影响，而墙之间的高度，才会对匹配产生影响。分别对猪和大象求差分（实际上就是用后面的减去前面的）判断最多能匹配几次。此外还要有一个特殊处理。当猪的墙长度为1的时候，一定能匹配n次（及大象的长度）

代码：

#include <bits/stdc++.h>
using namespace std;
int nexta[300000];
int a[300000],b[300000];
int s[300000],t[300000];
int n,w;
void getnexta()
{memset(nexta,0,sizeof(nexta));int k = -1,j = 0;nexta[0] = -1;while(j < w){if(k == -1||t[k] == t[j]){nexta[j + 1] = k + 1;j ++;k ++;}else{k = nexta[k];}}
}
int kmp()
{int ans= 0;getnexta();int i = 0,j = 0;while(i < n && j < w){if(j == -1 || s[i] == t[j]){i ++;j ++;}else{j = nexta[j];}if(j == w){ans ++;j = nexta[j];}}return ans;
}
int main()
{scanf("%d%d",&n,&w);for(int i = 0; i < n; i ++){scanf("%d",&a[i]);}for(int i = 0; i < w; i ++){scanf("%d",&b[i]);}if(w == 1){printf("%d\n",n);return 0;}n--,w--;for(int i = 0; i < n; i ++){s[i] = a[i + 1] - a[i];}for(int i = 0; i < w; i++){t[i] = b[i + 1] - b[i];}int ans = kmp();printf("%d\n",ans);
}