Codeforces Round #269 (Div. 2) D:http://codeforces.com/problemset/problem/471/D
题意：给定两个序列a ,b, 如果在a中存在一段连续的序列使得a[i]-b[0]==k, a[i+1]-b[1]==k.... a[i+n-1]-b[n-1]==k,就说b串在a串中出现过！最后输出b串在a串中出现几次！
题解：把两个串进行处理，相邻项之间做差，然后就很容易想到用KMP来搞，然后注意几个特判就行。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1000005
using namespace std;
long long next[N];
long long s1[N];//模板串
long long s2[N];//主串
int len1,len2,ans;
long long a[N],b[N];
void getnext(int plen){
int i = ,j = -;
next[] = -;
while( i<plen ){
if(j==-||s1[i]==s1[j]){
++i;++j;
//if(s1[i]!=s1[j] )这里别隐去的的部分，也可以不划去
next[i] = j;
// else
// next[i] = next[j];
}
else
j = next[j];
}
}
void KMP(){
getnext(len1);
int i = ,j = ;
while (i<len2&&j<len1){
if( j == - || s2[i] == s1[j] ){
++i;
++j;
}
else {
j = next[j]; }
if( j==len1 ){//找到一个匹配串之后，不是在原来串中往后移动一位，而是移动i-(j-next[j]);
ans++;
j=next[j];
}
}
}
int n,m;
int main(){
scanf("%d%d",&n,&m);
ans=;
for(int i=;i<=n;i++){
scanf("%I64d",&a[i]);
}
for(int j=;j<=m;j++){
scanf("%I64d",&b[j]);
}
for(int i=;i<=n;i++){
a[i-]=a[i]-a[i-]+1e9;
s2[i-]=a[i-];
// printf("%I64d " ,s2[i-2]);
}
//puts("");
for(int i=;i<=m;i++){
b[i-]=b[i]-b[i-]+1e9;
s1[i-]=b[i-];
//printf("%I64d " ,s1[i-2]);
}
if(n==&&m==)puts("");
else if(n==&&m!=)puts("");
else if(m==&&n!=)printf("%d\n",n);
else{
len2=n-;
len1=m-;
getnext(m-);
KMP();
printf("%d\n",ans);
}
}