BZOJ2384：[CEOI2014]Match

浅谈\(KMP\)：https://www.cnblogs.com/AKMer/p/10438148.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2384

这是一种特殊的\(KMP\)。匹配不再是直接判断相等了。

假设现在\([1,j]\)和\([i-j,i-1]\)已经匹配上了，我要判断\(j+1\)与\(i\)是否能继续扩展。

其实很简单，我们只需要判断在\([1,j]\)里面\(j+1\)这一位的前驱和后继与\(j+1\)的相对位置是否在\([i-j,i-1]\)里面与\(i\)也满足同样的关系即可。

前驱和后继的相对位置可以利用链表倒着扫一遍求出来。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=1e6+5;

int n,m,ans[maxn];
int pos[maxn],pre[maxn],nxt[maxn];
int a[maxn],b[maxn],s1[maxn],s2[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

bool check(int *x,int j,int i) {
    return (!a[j]||x[i-a[j]]<x[i])&&(!b[j]||x[i-b[j]]>x[i]);
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++) {
        s1[pos[i]=read()]=i;
        pre[i]=i-1,nxt[i]=i+1;
    }
    for(int i=1;i<=m;i++)s2[i]=read();
    for(int i=n;i;i--) {
        a[i]=pre[s1[i]]?i-pos[pre[s1[i]]]:0;
        b[i]=nxt[s1[i]]!=n+1?i-pos[nxt[s1[i]]]:0;
        if(pre[s1[i]])nxt[pre[s1[i]]]=nxt[s1[i]];
        if(nxt[s1[i]]!=n+1)pre[nxt[s1[i]]]=pre[s1[i]];
    }
    memset(nxt,0,sizeof(nxt));
    for(int i=2,j=0;i<=n;i++) {
        while(j&&(!check(s1,j+1,i)))j=nxt[j];
        if(check(s1,j+1,i))j++;nxt[i]=j;
    }
    for(int i=1,j=0;i<=m;i++) {
        while(j&&(!check(s2,j+1,i)))j=nxt[j];
        if(check(s2,j+1,i))j++;
        if(j==n) {ans[++ans[0]]=i-n+1,j=nxt[j];}
    }
    printf("%d\n",ans[0]);
    for(int i=1;i<=ans[0];i++)
        printf("%d ",ans[i]);
    return 0;
}

BZOJ2384：[CEOI2014]Match

原文：https://www.cnblogs.com/AKMer/p/10444735.html