Matching

对于整数序列 \((a_1,a_2,\cdots,a_n)\) 和 \(1\sim n\) 的排列 \((p_1,p_2,\cdots,p_n)\)，称 \((a_1,a_2,\cdots,a_n)\) 符合 \((p_1,p_2,\cdots,p_n)\)，当且仅当： - \(\{a\}\) 中任意两个数字互不相同； - 将 \((a_1,a_2,\cdots,a_n)\) 从小到大排序后，将会得到 \((a_{p_1},a_{p_2},\cdots,a_{p_n})\)。 现在给出 \(1\sim n\) 的排列 \(\{p\}\) 和序列 \(h_1,h_2,\cdots,h_m\)??，请你求出哪些 \(\{h\}\) 的子串符合排列 \(\{p\}\)。

对于 \(100\%\) 的数据，有 \(2\le n\le m\le 1\ 000\ 000;1\le h_i\le 10^9;1\le p_i\le n\)，保证 \(\{h\}\) 中的元素互不相同，且 \(\{p\}\) 是一个排列。

题解

https://www.luogu.com.cn/blog/118846/solution-p4696

重新实现KMP过程，比较简单的思路就是判断排名是否一致，可以离散化+树状数组解决。时间复杂度 \(O(n \log n)\)。

还有更快的方法，只判断值域的前驱后继的大小关系是否一致。时间复杂度 \(O(n)\)。

CO int N=1e6+10;
int a[N],b[N];
int pre[N],nex[N],L[N],R[N];
int fa[N],s[N];

IN bool check(int p[],int i,int u){
    return p[u+L[i]]<=p[u] and p[u+R[i]]>=p[u];
}
int main(){
    int n=read<int>(),m=read<int>();
    for(int i=1;i<=n;++i){
        read(b[i]); // rank -> index
        a[b[i]]=i; // index -> rank
        pre[i]=i-1,nex[i]=i+1; // two-way linked-list
    }
    for(int i=n;i>=1;--i){
        int j=a[i];
        if(pre[j]>=1) L[i]=b[pre[j]]-i;
        if(nex[j]<=n) R[i]=b[nex[j]]-i;
        pre[nex[j]]=pre[j],nex[pre[j]]=nex[j];
    }
    for(int i=2;i<=n;++i){
        int j=fa[i-1];
        while(j and !check(a,j+1,i)) j=fa[j];
        fa[i]=j+check(a,j+1,i);
    }
    for(int i=1;i<=m;++i) read(s[i]);
    vector<int> ans;
    for(int i=1,j=0;i<=m;++i){
        while(j and !check(s,j+1,i)) j=fa[j];
        j+=check(s,j+1,i);
        if(j==n){
            ans.push_back(i-n+1);
            j=fa[j];
        }
    }
    printf("%zd\n",ans.size());
    for(int x:ans) printf("%d ",x);
    puts("");
    return 0;
}

LG4696 Matching

原文：https://www.cnblogs.com/autoint/p/12334745.html