秋实大哥の恋爱物语

//裸kmp，劳资居然不会写！！！！！！

题意：中文题面自己看

解：差分+裸kmp

因为可以上下移动，所以只要变化趋势相符就行，于是我们先做一个差分，计算出后一个数与前一个数的差值，然后再跑kmp

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string>

using namespace std;

int n,m;
int a[2000007];
int b[2000007];
int f[2000007];

void getfail(){
    f[0]=0;
    f[1]=0;
    for (int i=1;i<m-1;i++){
            int now=f[i];
            while (now!=0 && b[now]!=b[i]) now=f[now];
            if (b[now]==b[i])
                f[i+1]=now+1;
            else
                f[i+1]=0;
    }
}

int main(){
    scanf("%d",&n);
    for (int i=0;i<n;i++){
            scanf("%d",&a[i]);
    }
    for (int i=0;i<n-1;i++) a[i]=a[i+1]-a[i];
    scanf("%d",&m);
    for (int i=0;i<m;i++){
            scanf("%d",&b[i]);
    }
    for (int i=0;i<m-1;i++) b[i]=b[i+1]-b[i];
    getfail();
    int now=0;
    int ans=0;
    for (int i=0;i<n-1;i++){
            while(now!=0 && a[i]!=b[now]) now=f[now];
            if (b[now]==a[i]) now++;
            if (now==m-1){
                    ans++;
                    now=f[now];
            }
    }
    if (ans==0)
        printf("Oh. That's impossible. I must have had a dream.\n");
    else
    {
        printf("Wow! Life Winner!\n");
        printf("%d\n",ans);
    }
    return 0;
}
/*
14
1 1 5 5 6 6 5 4 4 3 3 2 2 1
14
0 0 4 4 5 5 4 3 3 2 2 1 1 0

20
1 2 1 2 1 2 1 2 1 1 0 1 3 2 3 2 7 6 7 2
3
6 5 6

25
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
3
2 3 3

29
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
8
6 6 7 5 5 6 4 4

26
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
5
1 1 0 1 1
*/