Matching「CEOI2011」

【题目描述】
对于整数序列 \((a_1,a_2,a_3,\cdots,a_n)\) 和 \(1 \sim n\) 的排列 \((p_1,p_2,p_3,\cdots,p_n)\)，称 \((a_1,a_2,a_3,\cdots,a_n)\) 符合 \((p_1,p_2,p_3,\cdots,p_n)\)，当且仅当

• \(a\)中任意两个数字互不相同


• 将\(a\) 从小到大排序后，将会得到 \((a_{p_1},a_{p_2},a_{p_3},\cdots,a_{p_n})\) 。

现在给出 \(1 \cdots n\) 的排列 \(\{p\}\) 和序列 \(\{h\}\)，求出哪些 \(\{h\}\) 的子串符合排列 \(\{p\}\)。

【输入格式】
第一行两个空格隔开的正整数 \(n,m\)。
第二行 \(n\) 个空格隔开的正整数，表示排列 \(p\)。
第三行 \(m\) 个空格隔开的正整数，表示序列 \(h\)。

【输出格式】
第一行一个整数 \(k\)，表示符合 {p}{p} 的子串个数。
第二行 \(k\) 个空格隔开的正整数，表示这些子串的起始位置（编号从 \(1\) 开始）。请将这些位置按照从小到大的顺序输出。特别地，若 \(k=0\)，那么你也应当输出一个空行。

虽然说看起来不像 但是这题是个KMP匹配

注意到 对于一个数组\(a_{1 \sim n}\)，其中\(a_i\)表示第\(i\)个数在\(n\)个数中的相对大小是第\(a_i\)大，假设另一个数组\(cnt_{1 \sim n}\) 表示第\(i\)个数前面有\(cnt_i\)个数比它大，那么这样的一个\(cnt\)数组和\(a\)数组是一一对应的。以样例\(2,1,4,5,3\)为例 对应的\(cnt\)数组是\(0,0,2,3,2\)

于是 我们把原题转变为了求 \(\{h\}\)中的一段长为\(n\)的子串 对应的\(cnt\)数组 和 排列\(\{p\}\)对应的\(cnt\)数组相等
这里直接暴力枚举是\(O(nm)\)的 肯定会炸

所以考虑用KMP的思想 令\(nxt[i]\)表示排列\(\{p\}\)中最长的 前缀的\(cnt\)数组和后缀的\(cnt\)数组相同 的长度(类似KMP)
求法就和KMP差不多 具体见代码
主要是如何快速求出\(cnt\)数组呢？这个用树状数组或线段树就能很容易的实现 每次在 当前数的值 的位置单点修改+1(即上文第二段的\(a_i\)) 然后查询\(1 \sim a_i-1\)的和
以样例为例 \(2,1,4,5,3\)
第一次让位置2 ++ 然后查询\(1 \sim 1\) 得到0
第二次让位置1 ++ 查询\(1 \sim 0\) 得到0
第三次让位置4 ++ 查询\(1 \sim 3\) 得到2
以此类推

注意题目中的\(\{h\}\)序列需要离散化处理一下 剩下的就是和KMP差不多的匹配了 注意每次失配时把失配扔掉的那些元素在树状数组上-1

代码

#include <cstdio>
#include <iostream> 
#include <algorithm>
#include <cstring>
#define lowbit(x) x&(-(x))
using namespace std;

int n, m, sz;
int q[1000010], h[1000010], srt[1000010], cnt[1000010];
int tr[1000010];
int nxt[1000010];
int ans[1000010];

void updata(int ind, int x) {
    while (ind <= m) {
        tr[ind] += x;
        ind += lowbit(ind);
    }
}

int getsum(int ind) {
    int ret = 0;
    while (ind) {
        ret += tr[ind];
        ind -= lowbit(ind);
    }
    return ret;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);
        q[a] = i;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &h[i]);
        srt[i] = h[i];
    }
    sort(srt + 1, srt + m + 1);
    int len = unique(srt + 1, srt + m + 1) - srt - 1;
    for (int i = 1; i <= m; i++) {
        h[i] = lower_bound(srt + 1, srt + len + 1, h[i]) - srt;
    }
    cnt[n + 1] = -0x7fffffff;
    for (int i = 1; i <= n; i++) {
        cnt[i] = getsum(q[i]);
        updata(q[i], 1);
    }
    for (int i = 1; i <= m; i++) {
        tr[i] = 0;
    }
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && getsum(q[i]) != cnt[j + 1]) {
            for (int k = i - j; k < i - nxt[j]; k++) updata(q[k], -1);
            j = nxt[j];
        }
        if (getsum(q[i]) == cnt[j + 1]) {
            j++; updata(q[i], 1);
        }
        nxt[i] = j;
    }
    for (int i = 1; i <= m; i++) {
        tr[i] = 0;
    }
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && getsum(h[i]) != cnt[j + 1]) {
            for (int k = i - j; k < i - nxt[j]; k++) updata(h[k], -1);
            j = nxt[j];
        }
        if (getsum(h[i]) == cnt[j + 1]) {
            j++;
            updata(h[i], 1);
        }
        if (j == n) {
            ans[++sz] = i - n + 1;
        }
    }
    printf("%d\n", sz);
    for (int i = 1; i <= sz; i++) {
        printf("%d ", ans[i]);
    }
    puts("");
    return 0;
}

Matching「CEOI2011」

原文：https://www.cnblogs.com/ak-dream/p/AK_DREAM21.html