题解 P4696 【[CEOI2011]Matching】

· · 题解

kmp搞一搞

找到转化后的p排列，对于每个位置，之前比它大的最小的位置和比它小的最大的位置。

然后就kmp搞一搞就好啦。只不过原来的kmp是判断字母相同，现在是判断放这个数合不合法，其余的相同。

这个方法是线性的

#include<cstdio>
const int N=1e6+50;
inline void rad(int &_){
    static char ch;
    while(ch=getchar(),ch<'0'||ch>'9');_=ch-48;
    while(ch=getchar(),ch<='9'&&ch>='0')_=_*10+ch-48;
}
int Out[10],out;
inline void prt(int u){
    if(!u)++out;
    else for(;u;Out[++out]=u%10,u/=10);
    for(;out;putchar(48+Out[out--]));
    putchar(' ');
}
int n,m,x,ans;
int a[N],b[N],c[N],kmp[N];
int pre[N],net[N],L[N],R[N],Ans[N];
inline bool get(int *p,int u,int v){
    return (!L[u]||p[v+L[u]]<p[v])&&(!R[u]||p[v+R[u]]>p[v]);
    //判断合不合法
}
int main(){
    rad(n);rad(m);
    for(int i=1;i<=n;i++){
        rad(b[i]);a[b[i]]=i;
        pre[i]=i-1;net[i]=i+1;
    }
    //a[]即为转化后的p数组
    for(int i=n;i>=1;i--){
        x=a[i];
        if(pre[x])L[i]=b[pre[x]]-i;
        if(net[x]<=n)R[i]=b[net[x]]-i;
        pre[net[x]]=pre[x];
        net[pre[x]]=net[x];
    }
    //双向链表求比它大的最小的位置和比它小的最大的位置
    x=0;
    for(int i=2;i<=n;i++){
        while(x&&!get(a,x+1,i))x=kmp[x];
        if(get(a,x+1,i))x++;
        kmp[i]=x;
    }
    //先自身匹配
    x=0;
    for(int i=1;i<=m;i++)rad(c[i]);
    for(int i=1;i<=m;i++){
        while(x&&!get(c,x+1,i))x=kmp[x];
        if(get(c,x+1,i))x++;
        if(x==n)Ans[++ans]=i-n+1,x=kmp[x];
    }
    //然后与h串匹配
    prt(ans);putchar('\n');
    for(int i=1;i<=ans;i++)prt(Ans[i]);
}