//裸kmp，劳资居然不会写！！！！！！
题意：中文题面自己看
解：差分+裸kmp
因为可以上下移动，所以只要变化趋势相符就行，于是我们先做一个差分，计算出后一个数与前一个数的差值，然后再跑kmp
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #include<stack> 11 #include<string> 12 13 using namespace std; 14 15 int n,m; 16 int a[2000007]; 17 int b[2000007]; 18 int f[2000007]; 19 20 void getfail(){ 21 f[0]=0; 22 f[1]=0; 23 for (int i=1;i<m-1;i++){ 24 int now=f[i]; 25 while (now!=0 && b[now]!=b[i]) now=f[now]; 26 if (b[now]==b[i]) 27 f[i+1]=now+1; 28 else 29 f[i+1]=0; 30 } 31 } 32 33 int main(){ 34 scanf("%d",&n); 35 for (int i=0;i<n;i++){ 36 scanf("%d",&a[i]); 37 } 38 for (int i=0;i<n-1;i++) a[i]=a[i+1]-a[i]; 39 scanf("%d",&m); 40 for (int i=0;i<m;i++){ 41 scanf("%d",&b[i]); 42 } 43 for (int i=0;i<m-1;i++) b[i]=b[i+1]-b[i]; 44 getfail(); 45 int now=0; 46 int ans=0; 47 for (int i=0;i<n-1;i++){ 48 while(now!=0 && a[i]!=b[now]) now=f[now]; 49 if (b[now]==a[i]) now++; 50 if (now==m-1){ 51 ans++; 52 now=f[now]; 53 } 54 } 55 if (ans==0) 56 printf("Oh. That's impossible. I must have had a dream. "); 57 else 58 { 59 printf("Wow! Life Winner! "); 60 printf("%d ",ans); 61 } 62 return 0; 63 } 64 /* 65 14 66 1 1 5 5 6 6 5 4 4 3 3 2 2 1 67 14 68 0 0 4 4 5 5 4 3 3 2 2 1 1 0 69 70 20 71 1 2 1 2 1 2 1 2 1 1 0 1 3 2 3 2 7 6 7 2 72 3 73 6 5 6 74 75 25 76 2 3 2 3 3 2 3 3 3 2 3 2 2 3 3 2 2 2 3 3 3 3 2 3 3 77 3 78 2 3 3 79 80 29 81 6 6 7 5 5 6 4 4 5 3 3 4 2 2 3 1 1 2 0 0 1 -1 -1 0 -2 -2 -1 -3 -3 82 8 83 6 6 7 5 5 6 4 4 84 85 26 86 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 87 5 88 1 1 0 1 1 89 */