P4696-Matching

Iratis · 2022-02-03 17:45:30 · 题解

前言

很适合练习 KMP 的一道紫。

本文链表使用链表的做法。

解法

首先我们发现读入的序列 p 并不方便操作，所以我们可以先将 p 进行改动，从而成为一个模式串 v 。

然后我们就遇到了一个棘手的问题，应该如何求出每个数之间的大小关系，有部分题解使用了树状数组，而链表同样可以解决。从大到小，记录出每一个数字 v_i 的前驱 v_i-1 在 p 中的位置，与后继 v_i+1 在 p 中的位置。

最后便可直接使用 KMP 求解，只需更改一下判断两个位置是否能接上的函数：

bool check1(int n1,int n2)
{
    bool flag=true;
    if(les[n1]&&val[n2-(n1-les[n1])]>=val[n2])flag=false;
    if(mor[n1]&&val[n2-(n1-mor[n1])]<=val[n2])flag=false;
    return flag;
}
bool check2(int n1,int n2)
{
    bool flag=true;
    if(les[n1]&&h[n2-(n1-les[n1])]>=h[n2])flag=false;
    if(mor[n1]&&h[n2-(n1-mor[n1])]<=h[n2])flag=false;
    return flag;
}

最后是完整代码：

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
int p[1000001],h[1000001];
int pos[1000001],val[1000001];
int les[1000001],mor[1000001];
int nex[1000001];
int ans,ge[1000001];
struct Node
{
    int next,prev;
}node[1000001];
bool check1(int n1,int n2)
{
    bool flag=true;
    if(les[n1]&&val[n2-(n1-les[n1])]>=val[n2])flag=false;
    if(mor[n1]&&val[n2-(n1-mor[n1])]<=val[n2])flag=false;
    return flag;
}
bool check2(int n1,int n2)
{
    bool flag=true;
    if(les[n1]&&h[n2-(n1-les[n1])]>=h[n2])flag=false;
    if(mor[n1]&&h[n2-(n1-mor[n1])]<=h[n2])flag=false;
    return flag;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        val[p[i]]=i;
    }
    for(int i=1;i<=m;i++)scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)pos[i]=p[i];
    for(int i=1;i<=n;i++)node[i].next=i+1,node[i].prev=i-1;
    for(int i=n;i>=1;i--)
    {
        les[i]=pos[node[val[i]].prev];
        mor[i]=pos[node[val[i]].next];
        node[node[val[i]].next].prev=node[val[i]].prev;
        node[node[val[i]].prev].next=node[val[i]].next;
    }
    for(int i=1;i<=n;i++)
    {
        int j=nex[i-1];
        while(j>0&&check1(j+1,i)==false)j=nex[j];
        if(check1(j+1,i)==true&&j+1<i)j++;
        nex[i]=j;
    }
    int j=0;
    for(int i=1;i<=m;i++)
    {
        while(j>0&&check2(j+1,i)==false)j=nex[j];
        if(check2(j+1,i)==true)j++;
        if(j==n)
        {
            j=nex[j];
            ge[++ans]=i-n+1;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)printf("%d ",ge[i]);
    return 0;
}