跳转至

Y239 字符匹配

温馨提示：全文无废话，请一个字一个字仔细阅读，重点句已加粗。

题目大意

定义两个序列相似，当且仅当它们长度相等，且两序列相同位置的数字在整个序列中的排名相等。形式化的，设 \(A,B\) 是两个序列，若 \(\forall i,rank(a_i,a)=rank(b_i, b)\)，则 \(A,B\) 相似，其中 \(rank(a_i,a)\) 表示 \(a_i\) 在序列 \(a\) 中的排名。

现在，给出两个序列 \(s\) 和 \(t\)，求 \(s\) 有多少个子串和 \(t\) 相似，并输出它们的位置。

题解

先讲大致思路： 考虑使用 KMP 进行匹配。首先我们需要将序列转换为能用KMP匹配的样子。我们注意到，\(\forall i,rank(a_i,a)=rank(b_i, b)\) 的充要条件是，对于每个数，其前驱和后继以及与其相同的数字的位置在两个序列中相等。这样，我们可以通过预处理每个数字的前驱后继等等的位置，并用这些位置做KMP匹配。 （前驱定义为比该数小的最大的数，后继为比该数大的最小的数）

具体的，我们设 \(C_{i,0}\) 表示序列 \(t\) 的 \([1,i]\) 区间中，所有前驱中（因为序列可以重复）最靠右的一个，的位置；\(C_{i,1}\) 则表示序列的 \([1,i]\) 区间中，所有和 \(t_i\) 相等的数中，最靠右的一个，的位置；\(C_{i,2}\) 表示序列的 \([1,i]\) 区间中，所有后继中最靠右的一个，的位置。

我们考虑如何进行匹配。当 \(t_j\) 在 \([1,j]\) 中不存在前驱，或者 \(t_{C_{j,0}}<t_i\)，则前驱匹配；当 \(t_j\) 在 \([1,j]\) 中不存在与其相等的数，或者 \(t_{C_{j,1}}=t_i\)，则相等的数匹配；当 \(t_j\) 在 \([1,j]\) 中不存在后继，或者 \(t_{C_{j,0}}>t_i\)，则后继匹配。若前驱、相等、后继都匹配，则该位匹配；所有位都匹配是两字符串相似的充要条件。

“所有位都匹配是两字符串相似的充要条件” 不是很容易直接看出来，所以我们考虑使用数学归纳法进行证明。必要性可由定义直接推出，这里只证充分性。我们假设 \([1,i-1]\) 区间内序列 \(s\) 和序列 \(t\) 已经匹配，两字符串的 \([1,i-1]\) 前缀相似。

Ⅰ. \(T\) 中区间 \([1,i-1]\) 存在一个与 \(T_i\) 相等的数字： 若 \(S_{C_{i,1}}=S_i\)，则 \(S_i\) 的排名和 \(S_{C_{i,1}}\) 相等；又因为 \(T_i\) 和 \(T_{C_{i,1}}\) 排名相等，同时由于 \([1,i]\) 已经匹配，所以 \(S_{C_{i,1}}\) 和 \(T_{C_{i,1}}\) 排名相等，证毕。

Ⅱ. \(T\) 中区间 \([1,i-1]\) 中不存在一个与 \(T_i\) 相等的数字： 根据定义，\(T_{C_{i,0}}\) 和 \(T_{C_{i,2}}\) 在 \([1,i-1]\) 中排名相邻，则 \(S_{C_{i,0}}\) 和 \(S_{C_{i,2}}\) 排名也相邻。若第 \(i\) 位匹配，即满足 \(S_{C_{i,0}}<S_i<S_{C_{i,2}}\)，则在 \([1,i]\) 区间中 \(\(rank(S_{C_{i,0}})<rank(S_i)<rank(S_{C_{i,2}})\)\) 同时根据 \(C\) 的定义有 \(\(rank(T_{C_{i,0}})<rank(T_i)<rank(T_{C_{i,2}})\)\) 又因为 \(\(rank(S_{C_{i,0}})=rank(T_{C_{i,0}})\)\) \(\(rank(S_{C_{i,2}})=rank(T_{C_{i,2}})\)\) 所以 \(rank(S_i)=rank(T_i)\)，充分性证毕。

既然证完了，先维护 \(C_{i,j}\)，再直接根据上文关于“每位匹配的定义”做KMP即可。

Note 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
const int N = 5E5 + 10;
const int K = 1E4 + 10;

int n, m, k;
int a[N], b[N];
int p[N];

int c[N][3];
int last[K];

set<int> st;

int cnt, ans[N];

int main() {

    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    for(int i = 1; i <= m; i++) {
        auto pit = st.lower_bound(b[i]);
        auto sit = st.upper_bound(b[i]);
        if(pit != st.begin()) {
            pit--;
            c[i][0] = i - last[*pit];
        }
        if(last[b[i]] != 0) c[i][1] = i - last[b[i]];
        if(sit != st.end()) c[i][2] = i - last[*sit];
        st.insert(b[i]);
        last[b[i]] = i;
    }

    for(int i = 2, j = 0; i <= m; i++) {
        while(j > 0 && !(
            (c[j + 1][0] == 0 || b[i - c[j + 1][0]] < b[i]) && 
            (c[j + 1][1] == 0 || b[i - c[j + 1][1]] == b[i]) && 
            (c[j + 1][2] == 0 || b[i - c[j + 1][2]] > b[i])))
            j = p[j];
        if(
            (c[j + 1][0] == 0 || b[i - c[j + 1][0]] < b[i]) && 
            (c[j + 1][1] == 0 || b[i - c[j + 1][1]] == b[i]) && 
            (c[j + 1][2] == 0 || b[i - c[j + 1][2]] > b[i])) 
            j++;
        p[i] = j;
    }

    for(int i = 1, j = 0; i <= n; i++) {
        while(j > 0 && !(
            (c[j + 1][0] == 0 || a[i - c[j + 1][0]] < a[i]) && 
            (c[j + 1][1] == 0 || a[i - c[j + 1][1]] == a[i]) && 
            (c[j + 1][2] == 0 || a[i - c[j + 1][2]] > a[i])))
            j = p[j];
        if(
            (c[j + 1][0] == 0 || a[i - c[j + 1][0]] < a[i]) && 
            (c[j + 1][1] == 0 || a[i - c[j + 1][1]] == a[i]) && 
            (c[j + 1][2] == 0 || a[i - c[j + 1][2]] > a[i])) 
            j++;
        if(j == m) {
            ans[++cnt] = i - m + 1;
            j = p[j];
        }
    }

    cout << cnt << endl;
    for(int i = 1; i <= cnt; i++) {
        cout << ans[i] << endl;
    }


    return 0;
}