BISHI10　小红的字符串修改¶

简单通过率 42.74%python3样例通过牛客 AC字符串模拟

一句话

把 s 改成 t 的某个连续子串，求最少替换次数。

解题思路¶

这题考什么¶

两层观察，缺一不可。第一层，替换只改字母、不改长度也不改位置，所以 s 最终必须与 t 中某一段长度恰为 |s| 的连续区间逐位对齐。可选的对齐位置只有 |t| - |s| + 1 个，把它们枚举一遍就穷尽了所有可能，不需要更复杂的匹配。第二层，每一位的改动代价与其他位互不影响，且字母表首尾相接（'a' 与 'z' 相邻），所以把 x 改成 y 的代价是环上的距离 min(|x - y|, 26 - |x - y|)。两层合起来：答案 = 每个对齐位置上 |s| 个字母的环距离之和的最小值。

实现上先把 26 * 26 种字母对的代价打成一张扁平表 cost，再用 map 把「查表 + 求和」整体交给 C 层，省掉 1e6 次 Python 层的取绝对值和比较。相关基础见 70-字符串处理。

数据规模与复杂度¶

|s|, |t| <= 1e3，对齐位置至多 1e3 个，每个位置比对至多 1e3 位，合计 1e6 次查表，复杂度 O(|s| * (|t| - |s| + 1))。纯 Python 的双重 for 循环在 1e6 这个量级上是零点几秒，仍在「其他语言 2 秒」以内；换成 map + sum 之后余量更充足。

坑在哪¶

'a' 和 'z' 相邻，代价必须取环上距离 min(d, 26 - d)。直接写 abs(ord(x) - ord(y)) 会把 'a' -> 'z' 算成 25，实际只要 1 步，样例 2（zzzzzz / xyzabc）的答案 9 正是靠环形距离才凑得出来；
题面的「子串」是连续子串（从开头和结尾各删去若干字符得到），不是子序列，所以只需定长滑动，不必上动态规划；
题面保证 |t| >= |s|，故 m - n + 1 >= 1，min() 不会遇到空序列；
代价表是一维的，按「行首偏移 + 列号」寻址：base 里存的是 (字母编号 * 26) 而不是字母编号本身，这样后面一次加法就能算出扁平下标，把乘法从内层循环里彻底挪走。

样例复核¶

s = "abc"、t = "abbc"。对齐到 t[0:3] = "abb"：a->a 0 次、b->b 0 次、 c->b 1 次，合计 1；对齐到 t[1:4] = "bbc"：1 + 0 + 0 = 1。最小值 1，与样例一致。

参考实现¶

solutions/BISHI10.py
import sys
from operator import add

data = sys.stdin.buffer.read().split()
s = data[0].decode()
t = data[1].decode()
n, m = len(s), len(t)

# 扁平化的 26*26 代价表：cost[i * 26 + j] = 字母 i 变到字母 j 的最少次数
cost = [min(abs(i - j), 26 - abs(i - j)) for i in range(26) for j in range(26)]

base = [(ord(c) - 97) * 26 for c in s]     # s 每一位在代价表中的行首偏移
tc = [ord(c) - 97 for c in t]              # t 每一位的字母编号

# 枚举 s 在 t 中的起始对齐位置；map(add, ...) 把「行首 + 列号」的下标计算放到 C 层
# tc[off:off + n] 取出与 s 等长的那一段，两个序列逐位相加即得各位的查表下标
best = min(sum(map(cost.__getitem__, map(add, base, tc[off:off + n])))
           for off in range(m - n + 1))
print(best)

BISHI10 小红的字符串修改¶