c_wInf's blog
0%

Ave Musica 题解

Posted on Edited on

ACMOJ链接

形式化题意

给定长度为 \(n\) 的字母序列 \(S\) ，和长度为 \(m\) 的字母序列 \(T\) ，求 \(S\) 中和 \(T\) 相似的子串有多少个，相似代表离散化后一致，即每一个对应位置字符的序关系保持一致。

切入

我们联想到KMP算法：KMP中的匹配是字串每一个字符都相等，而这里的匹配条件更加宽松，只要离散化后相等即可。考虑到KMP的想法是每次判断下一个字符是否匹配，匹配就继续，不匹配就跳转，容易想到这里我们只需要修改每次匹配下一个字符时匹配的逻辑即可。

从某一个位置开始， \(S\) 的长度为 \(i\) 的子串已经和 \(T\) 的长度为 \(i\) 的子串相似。那么我们只需要找到在此基础上，让长度为 \(i+1\) 的子串匹配的条件即可。

不难发现前 \(i\) 个字符已经满足对应的序关系，只需要让第 \(i+1\) 个字符满足和前 \(i\) 个字符相容的序关系即可。即，在 \(S\) 的子串和 \(T\) 中，都满足比第 \(i+1\) 个字符大的最小字符和比其小的最大字符是同一个字符即可，分别记作 \(up\) 和 \(down\) 。（当然，在这里，这样的字符可能有多个，它们也会是一一对应的。）换言之，第 \(i+1\) 个字符与 \(up\) 和 \(down\) 保持了相同的序关系。

复杂度化简

我们考虑在KMP预处理时同时预处理 \(up\) 和 \(down\) 的位置。对于此题，我们只需要维护一个数组记录哪些字符已经出现过即可。复杂度 \(O (k^2)\) ，其中 \(k\) 是字符种类数，此题中为 \(26\) 。对于字符种类数较大的情形，这部分复杂度可以通过维护一个树状数组/线段树/平衡树来降低复杂度到 \(O (k \log k)\)

匹配时，只需要用 \(up\) 和 \(down\) 给出的限制条件替换KMP中的字符相等条件，然后在匹配失败时用 \(next\) 进行跳转即可，复杂度线性。

在预处理KMP中 \(next\) 数组时，也沿用KMP的思想，通过前面已经预处理好的部分 \(next\) 数组和 \(up\) 与 \(down\) 来将预处理复杂度减少到和匹配一样，即线性。

代码

为防止抄袭，仅展示kmp部分，匹配部分其实已经蕴含在kmp部分了。

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
constexpr unsigned K = 26;

bool single_match (int* ps, int up, int low) {
    if (up == low) return ps[-up] == *ps;
    if (up) {
        if (*ps >= ps[-up]) return false;
    }
    if (low) {
        if (*ps <= ps[-low]) return false;
    }
    return true;
}
/*************
ps => the pointer to the current matching position
up, low => the matching limit, indicating the relative position of the character to be compared

ps[-low] < *ps, *ps < ps[-up]

special cases:
up == 0 => no upper limit
low == 0 => no lower limit
up == low => ps[-low] == *ps, *ps == ps[-up]
*************/

void kmp (int* next, int* up, int* low, int* s, int m) {
    up[0] = low[0] = 0;

    int last_pos[K] = {};
    for (int i = 1; i <= m; ++i) {
        if (last_pos[s[i]]) {
            up[i] = low[i] = i - last_pos[s[i]];
        } else {
            int upx = s[i];
            for (; upx < K && !last_pos[upx]; ++upx) continue;
            if (upx == K)
                up[i] = 0;
            else
                up[i] = i - last_pos[upx];

            int lowx = s[i];
            for (; lowx >= 0 && !last_pos[lowx]; --lowx) continue;
            if (lowx == -1)
                low[i] = 0;
            else
                low[i] = i - last_pos[lowx];
        }

        last_pos[s[i]] = i;
    }

    next[0] = next[1] = 0;
    for (int i = 2, j = 0; i <= m; ++i) {
        for (; j > 0 && !single_match (s + i, up[j + 1], low[j + 1]); j = next[j]) continue;
        next[i] = ++j;
    }
}