题解 P4696 【[CEOI2011]Matching】

· · 题解

\Large\texttt{P4696}

更好的体验

标签：KMP，链表结构

前言

我靠网上怎么全是带 \log 的做法，看题目限制应该是放了一支 \log，但是由于我太菜没想出来，所以来写 \mathcal O(n) 的题解了。

似乎常数比较小。

题意

不做赘述，注意给定的序列 \{p\} 其实是类似于后缀数组中的 sa 数组，不是每个下标的排名。

思路

子串匹配问题，输出方案，哇这限制条件，这好 \mathcal O(n) 啊，而且是逐字匹配，感觉很像 KMP。

我们就先向 KMP 方向考虑，注意到输入序列 \{p\} 是以排名为下标，没有意义，转换成每个下标的排名数组，注意此时还是一个排列。

我们考虑一个成功的匹配是怎样的，即序列 \{a\} 的某一个子串离散化排序后对应的下标是和序列 \{p\} 完全一致的。

那我们如何重新定义这个 “匹配” 和 “一致”，如何在 KMP 建立正确的 next 数组中进行最优的比较操作？

在建立 next 的数组的过程中，当我们考虑到下标 i 时，我们假设已经像普通的 KMP 思路已经继承了 i - 1 的最优匹配，我们比较两个 i 和 next[i] + 1 （在比较序列 p[1,\dots,next[i - 1] + 1] 和 p[i - next[i - 1], \dots, i] 的意义下）是否相等，即比较 p[next[i - 1] + 1] 在其前缀序列的排名和 p[i] 在其后缀序列的排名是否相等，否则一直跳 next，正确性显然是对的。

到这里，是可以用树状数组做了。

对于 \mathcal O(n) 的做法，我们可以更好地利用一个性质：已匹配的两个字串排名是完全相等的，所以我们只需要比较一下 i 的前驱和后继与 next[i - 1] + 1 的前驱和后继（相对于分别的匹配子串的）位置是否相等，这样同样保证了两者在匹配子串的相对位置。

而我们只需要求得模式串的前驱和后继即可，将其拿来比较即可。

（这里的前驱和后继是指值小于/大于某个数，且下标小于某个数）

代码

-O2 854ms 目前最优解。

int a, b, s[2][N + 5], L[N + 5], R[N + 5], nxt[N + 5], p[N + 5], l[N + 5], r[N + 5];
vector<int> ans;

bool check(int o, int i, int j, int mn, int mx) {
    int res = 1;
    if (mn) res &= (s[o][i - (j - mn)] < s[o][i]);
    if (mx) res &= (s[o][i - (j - mx)] > s[o][i]);
    return res;
}

void init() {
    rep(i, 1, a) l[i] = p[s[0][i] - 1], r[i] = p[s[0][i] + 1];
    per(i, a, 1) {
        L[i] = l[i];
        R[i] = r[i];
        l[r[i]] = l[i];
        r[l[i]] = r[i];
    }
    int j = 0;
    rep(i, 2, a) {
        while (j && !check(0, i, j + 1, L[j + 1], R[j + 1])) j = nxt[j];
        if (check(0, i, j + 1, L[j + 1], R[j + 1])) ++j;
        nxt[i] = j;
    }
}

signed main() {
    // freopen("in1.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    a = read();
    b = read();
    rep(i, 1, a) p[i] = read();
    rep(i, 1, a) s[0][p[i]] = i;
    rep(i, 1, b) s[1][i] = read();
    init();
    int j = 0;
    rep(i, 1, b) {
        while (j && !check(1, i, j + 1, L[j + 1], R[j + 1])) j = nxt[j];
        if (check(1, i, j + 1, L[j + 1], R[j + 1])) ++j;
        if (j == a) ans.PB(i - a + 1), j = nxt[j];
    }
    printf("%d\n", siz(ans));
    rep(i, 0, siz(ans) - 1) printf("%d ", ans[i]);
    return 0;
}