HDU 4749 Parade Show（KMP变形）

题意：有一个文本数列，问可以匹配多少个模式数列（不允许重叠），但这里的“匹配”是这样定义：满足大小关系即可，比如（2，4，4，1）和（33，57，57，2）匹配

思路：明显可以把文本数列和模式数列处理一下，用i与i+1的关系差值代替

再KMP即可，KMP的时候由于不能重叠，所以匹配成功以后，文本串要向后移一位再接着匹配即可

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =  1e5+100;
int y[MAXN],x[MAXN];

int next1[MAXN];
bool nocmp(int x[],int i,int y[],int j)
{
    if(x[i]*y[j]>0) return false;
    if(x[i]==0&&y[j]==0) return false;
    return true;
}
void getnext(int x[],int m,int next1[])
{
    int i,j;
    j=next1[1]=0;
    i=1;
    while(i<=m)
    {
        while(j!=0&&nocmp(x,i,x,j))
            j=next1[j];
        next1[++i]=++j;
    }

}

int KMP(int x[],int m,int y[],int n)
{
    int i,j;
    int ans=0;
    getnext(x,m,next1);
    i=j=1;
    while(i<=n)
    {
        while(j!=0&&nocmp(y,i,x,j)) j=next1[j];
        i++;j++;
        if(j>m)
        {
            ans++;
            i++;
            j=1;
        }
    }
    return ans;
}
int main()
{
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k))
    {

        for(int i=1;i<=n;i++)
            scanf("%d",&y[i]);
        for(int i=1;i<n;i++)
            y[i]=y[i+1]-y[i];
        for(int i=1;i<=m;i++)
            scanf("%d",&x[i]);
        for(int i=1;i<m;i++)
            x[i]=x[i+1]-x[i];
        if(m==1) printf("%d\n",n);
        else printf("%d\n",KMP(x,m-1,y,n-1));
    }
    return 0;
}

HDU 4749 Parade Show（KMP变形）

原文：http://blog.csdn.net/kalilili/article/details/44648367