T31069: 禁用词的字符串构造

二分查找和预处理, prefix sum, http://cs101.openjudge.cn/practice/31069/

给定只包含小写字母的字符串 A, B ，以及 k 个禁止出现的长度为 2 的字符串（称为禁用组合）。

构造字符串 C 的方式如下：

1. C 起始是空串；
2. 按顺序枚举 A 的每个字符 Ai，依次与 B 的每个字符 Bj 组合成串 AiBj；
3. 若 AiBj 不在禁用组合中，则将该串按加入到 C 的末尾。

给定 q 个询问，每个询问给出 ti，求 C 的第 ti 个字符，保证所有询问都不会越界。

输入

第一行包含四个整数 LA, LB, k, q, 其中 LA, LB 分别为 A, B 的长度.. 第二行包含 LA 个小写字符, 表示字符串 A. 第三行包含 LB 个小写字符, 表示字符串 B. 接下来 k 行每行有两个小写字符, 用一个空格分开, 表示 k 组禁用组合. 接下来 q 行每行一个正整数, 第 i 个表示第 i 次询问对应的 ti. 注意字符串的下标从 0 开始. 记 C 的长度为 LC, 保证 0 <= ti < LC.

输出

共 q 行, 每行一个字符, 第 i 行的表示第 i 次询问的答案.

样例输入

4 2 2 10
cbaa
ac
b c
a a
0
1
2
3
4
5
6
7
8
9

样例输出

c
a
c
c
b
a
a
c
a
c

提示

对所有数据, LA, LB <= 200000, k <= 26^2, q <= 100000 . 对 60% 的数据: LA, LB <= 1000. 对另外 20% 的数据: q <= 10.

这是一个基于二分查找和预处理的算法设计。由于数据范围较大（$LA,LB\le 200,000$，$q\le 100,000$），直接构造出完整的字符串 $C$（其长度可能达到 $2\times LA\times LB\approx 8\times {10}^{10}$）在时间和空间上都是不可行的。因此，我们需要通过数学规律和预处理来快速定位每个询问字符。

解题思路

1. 观察字符串 $C$ 的构成：

   • 字符 $A_i$ 与 $B_j$ 组合：如果 $A_i{B}_j$ 不是禁用组合，则将 $A_i$ 和 $B_j$ 顺序放入 $C$。
   • 对于固定的 $A_i$，它与所有合法的 $B_j$ 拼接。由于 $B_j$ 的合法性仅取决于字符 $A_i$ 本身（只有 26 种可能），我们可以为 $A_i$ 的每个字符计算出它在 $C$ 中贡献的子串长度。
   • 令 $N(char)$ 为与字符 $char$ 组合不被禁用的 $B$ 中字符的数量。那么每个 $A_i$ 在 $C$ 中贡献的子串长度为 $2\times N(A_i)$。

2. 预处理：

   • 禁用组合：使用一个 $26\times 26$ 的布尔型二维数组 forbidden[u][v] 记录字符对是否被禁用。
   • 过滤后的 $B$ 串：对于字符 'a' 到 'z' 的每一个字符 $ch$（共 26 种可能），我们预先过滤出 $B$ 串中与其组合合法的字符序列，记作 B_filtered[ch]。其长度即为 $N(ch)$。
   • 前缀和定位：计算每个 $A_i$ 生成子串长度的前缀和数组 $P$。$P[i]$ 表示由 $A_0,A_1,\dots ,A_{i-1}$ 生成的子串总长度。
     • $P[0]=0$
     • $P[i+1]=P[i]+2\times \text{len}(B\mathrm{\_}filtered[A_i])$

3. 回答询问：

   • 对于每一次询问 $t$：
     • 利用二分查找在 $P$ 中找到最大的 $i$，使得 $P[i]\le t$。这说明第 $t$ 个字符落在了由 $A_i$ 产生的块中。
     • 计算块内相对偏移量 $rem=t-P[i]$。
     • 如果 $rem$ 是偶数，说明对应的字符是 $A_i$。
     • 如果 $rem$ 是奇数，说明对应的字符是 $B$ 中的字符。具体为 B_filtered[A_i][rem // 2]。

Python 代码实现

import bisect
import sys


def solve():
    # 快速读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    LA = int(input_data[0])
    LB = int(input_data[1])
    k = int(input_data[2])
    q = int(input_data[3])

    A = input_data[4]
    B = input_data[5]

    # 解析禁用组合
    forbidden = [[False] * 26 for _ in range(26)]
    idx = 6
    for _ in range(k):
        u = ord(input_data[idx]) - 97
        v = ord(input_data[idx + 1]) - 97
        forbidden[u][v] = True
        idx += 2

    # 解析询问
    queries = []
    for _ in range(q):
        queries.append(int(input_data[idx]))
        idx += 1

    # 预处理：对 26 个可能的 A 字符，过滤 B 中与之相配的字符序列
    B_filtered = ["" for _ in range(26)]
    for a_idx in range(26):
        # 找出对于字符 chr(97 + a_idx) 而言，不被禁用的 B 字符集合
        valid_set = {
            chr(97 + b_idx)
            for b_idx in range(26)
            if not forbidden[a_idx][b_idx]
        }
        # 过滤 B
        B_filtered[a_idx] = "".join([b for b in B if b in valid_set])

    # 预处理：计算前缀和 P
    P = [0] * (LA + 1)
    A_ord = [ord(char) - 97 for char in A]
    B_lengths = [len(B_filtered[i]) for i in range(26)]

    for i in range(LA):
        P[i + 1] = P[i] + 2 * B_lengths[A_ord[i]]

    # 回答询问
    out = []
    for t in queries:
        # 寻找 t 落在 A 的哪个字符块内
        idx_A = bisect.bisect_right(P, t) - 1
        rem = t - P[idx_A]

        if rem % 2 == 0:
            out.append(A[idx_A])
        else:
            out.append(B_filtered[A_ord[idx_A]][rem // 2])

    # 打印输出
    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：

  • 预处理：过滤 $B$ 串需要运行 26 次，每次遍历长度为 $LB$ 的字符串。这部分耗时 $26\times LB$。计算前缀和 $P$ 耗时 $O(LA)$。预处理总时间复杂度为 $O(26\times LB+LA)$。
  • 查询：每次查询使用一次二分查找，复杂度为 $O(\log LA)$。$q$ 次查询总耗时为 $O(q\log LA)$。
  • 对于最大数据规模（$LA,LB\le 200,000,q\le 100,000$），整体运行大约需要 $0.5$ 秒，完全能够满足时间限制。

• 空间复杂度：

  • 存储 B_filtered 的 26 个过滤后字符串的总长度不超过 $26\times LB$。
  • 前缀和数组 $P$ 长度为 $LA+1$。
  • 整体空间复杂度为 $O(26\times LB+LA+q)$，在最大数据下大约占用数十MB内存，符合常规空间限制。