第 70 章 字符串处理¶
配套例题：BISHI10 小红的字符串修改、BISHI123 环形字符串跃迁 来源：S1 菜鸟教程 Python3 字符串；S2
stl/string.cpp前置：04-字符串、21-复杂度与Python性能
04 章 讲的是「Python 的字符串有什么」， 这一章讲的是「算法竞赛里该用哪个」。
核心只有三句话：
str不可变——所有「逐字符修改」的写法都是 \(O(n^2)\)；bytes更快——索引出来是int，比较、比较、再比较都省一层对象；- 能不循环就不循环——
join/map/ 切片赋值把循环压到 C 层。
70.1 三种表示：str、bytes、list¶
| 表示 | 元素类型 | 可变 | 单元素内存 | 典型来源 |
|---|---|---|---|---|
str |
单字符 str |
❌ | 1–4 字节（紧凑存储） | input()、.decode() |
bytes |
int（0–255） |
❌ | 1 字节 | sys.stdin.buffer.read().split() |
bytearray |
int |
✅ | 1 字节 | bytearray(b"...") |
list[str] |
单字符 str |
✅ | 8 字节指针 | list(s) |
list[int] |
int |
✅ | 8 字节指针 | [ord(c) for c in s] |
最容易被忽略的一条：
⚠️ 在
bytes上索引得到的是整数，不是字符。 所以判断b[i] == '#'永远是False，必须写b[i] == ord('#')（或b[i] == 35）。 这是从str切到bytes时最高频的 bug。但切片仍然给
bytes：b[i:i+1] == b'#'也对，只是比整数比较慢。
竞赛里的默认选择¶
import sys
data = sys.stdin.buffer.read().split() # 每个 token 是 bytes
s = data[0] # 直接用 bytes，不 decode
不 decode 的三个理由：
| 理由 | 说明 |
|---|---|
| 快 | 省掉一次 \(O(n)\) 的解码 |
| 省内存 | bytes 一个字符 1 字节 |
| 比较更快 | b[i] == b[j] 是整数比较，s[i] == s[j] 是对象比较 |
什么时候必须 decode：需要用 str 专有方法（如格式化输出、str.title()）时。
但注意 bytes 其实也有 split、strip、find、replace、startswith、
count、join 等绝大多数方法，竞赛需要的基本都有。
70.2 str 不可变导致的 \(O(n^2)\) 陷阱¶
这是 Python 字符串最大的坑，04 章 已经讲过，这里补充四种典型场景和它们的正确写法。
场景一：循环拼接¶
\(n = 10^5\) 时，前者约 2 秒，后者约 0.01 秒——200 倍差距。
场景二：逐字符修改¶
# ❌ 这行根本不合法：TypeError: 'str' object does not support item assignment
s[i] = 'x'
# ✅ 写法 A：转成 list，改完再 join
t = list(s)
t[i] = 'x'
s = "".join(t)
# ✅ 写法 B（更快）：用 bytearray，全程整数
t = bytearray(s, "ascii") # 或者输入本来就是 bytes: bytearray(b)
t[i] = ord('x')
s = t.decode()
# ✅ 写法 C：只改一处时用切片拼接（O(n) 但常数极小）
s = s[:i] + 'x' + s[i + 1:]
| 写法 | 单次修改 | \(k\) 次修改 | 备注 |
|---|---|---|---|
A：list + join |
\(O(n)\) | \(O(n + k)\) | 通用，可读性好 |
B：bytearray |
\(O(1)\) | \(O(n + k)\) | 最快，且能切片赋值 |
| C：切片拼接 | \(O(n)\) | \(O(nk)\) ❌ | 只适合改一次 |
场景三：反复取前缀/后缀¶
# ❌ O(n^2)：每次切片都复制
for i in range(n):
pre = s[:i]
process(pre)
# ✅ 用哈希/前缀数组代替「真的切出来」
# 见 36-哈希与字符串哈希
切片是复制，不是视图。这一点和 C++ 的
string_view、Go 的 slice 都不一样。s[l:r]的代价是 \(O(r-l)\)，在循环里切大片就是平方级。 需要「不复制地引用子串」时，用(l, r)下标对 + 哈希。
场景四：构造答案串¶
# ❌
ans = ""
for i in range(n):
ans += "YES\n" if ok[i] else "NO\n"
print(ans)
# ✅ 攒进 list，最后一次 join + 一次 write
out = []
push = out.append
for i in range(n):
push("YES" if ok[i] else "NO")
sys.stdout.write("\n".join(out) + "\n")
见 20-输入输出处理。
bytearray 的切片赋值：让循环消失¶
bytearray 支持带步长的切片赋值，这是构造字符串时的杀手锏：
n = 5
s = b"abcde"
t = bytearray(b'#' * (2 * n + 1)) # '#a#b#c#d#e#'
t[1::2] = s # ★ 一次 C 层拷贝，把 s 铺到奇数位
# 埃氏筛也是同一个技巧（21 章）：
# is_p[i*i::i] = bytearray(len(range(i*i, n+1, i)))
Manacher 算法构造分隔串用的正是这一招（72-回文），
比 '#' + '#'.join(s) + '#' 快好几倍。
70.3 字符与 ASCII：ord / chr¶
必须记住的三个数字：'0' = 48，'A' = 65，'a' = 97。
字符 → 下标的标准写法¶
# str 输入
idx = ord(c) - 97 # 小写字母 -> 0..25
idx = ord(c) - 65 # 大写字母 -> 0..25
idx = ord(c) - 48 # 数字字符 -> 0..9
# bytes 输入（b[i] 已经是 int，省掉 ord 调用）
idx = b[i] - 97
| 场景 | 写法 |
|---|---|
| 26 个字母计数 | cnt = [0]*26; for ch in b: cnt[ch-97] += 1 |
| 大小写混合（52 种） | ch - 65 if ch < 97 else ch - 97 + 26，或直接用 ch 当下标开 128 大小的数组 |
| 判是否字母 | b'a' <= ch <= b'z'… ❌ 错，ch 是 int：写 97 <= ch <= 122 |
| 大小写转换 | ch ^ 32（ASCII 里大小写只差第 5 位！） |
| 字母表环形距离 | min(d, 26 - d)，其中 d = abs(x - y) |
ch ^ 32这个技巧：'a'= 0b1100001，'A'= 0b1000001，只差0b100000 = 32。 所以异或 32 就是翻转大小写，| 32是转小写，& ~32是转大写。 见 46-位运算。
字符计数：三种写法¶
from collections import Counter
# 写法一：Counter（最短，C 层循环）
c = Counter(s)
# 写法二：定长数组（值域已知时最快，省哈希）
cnt = [0] * 26
for ch in b: # b 是 bytes
cnt[ch - 97] += 1
# 写法三：bytes.count（只查少数几个字符时最快，纯 C）
k = s.count('a')
| 需求 | 选哪个 |
|---|---|
| 要全部 26 个字母的频次 | 定长数组（比 Counter 快 2–3 倍） |
| 字符集大/未知（Unicode） | Counter |
| 只关心一两个字符 | s.count(x)，纯 C 循环 |
| 要「出现次数最多的 k 个」 | Counter(s).most_common(k) |
70.4 分割与拼接的性能¶
| 操作 | 复杂度 | 是否 C 层 | 备注 |
|---|---|---|---|
s.split() |
\(O(n)\) | ✅ | 按任意空白切，顺带去掉换行 |
s.split(',') |
\(O(n)\) | ✅ | 指定分隔符 |
s.splitlines() |
\(O(n)\) | ✅ | 按行切 |
"".join(list_of_str) |
\(O(总长)\) | ✅ | 拼接的唯一正确写法 |
s + t |
$O( | s | + |
s * k |
$O(k | s | )$ |
s.replace(a, b) |
\(O(n)\) | ✅ | |
s.find(t) / t in s |
平均近 \(O(n)\) | ✅ | 内部是 Crochemore-Perrin 算法，见 71 章 |
s[::-1] |
\(O(n)\) | ✅ | 反转 |
s.strip() |
\(O(n)\) | ✅ |
split() vs split(' ')：一个经典坑¶
"a b".split() # ['a', 'b'] —— 连续空白算一个分隔符，且忽略首尾
"a b".split(' ') # ['a', '', 'b'] —— 空串也算一段！
"a\n".split() # ['a'] —— 换行也被当空白处理
"a\n".split(' ') # ['a\n'] —— 换行留在里面了！
竞赛里一律用无参数的
split()，除非分隔符真的是逗号之类的特定字符。 无参版还顺手帮你去掉了\r（Windows 换行）， 这在牛客上是实打实的救命细节。
join 的正确姿势¶
# ❌ 会 TypeError：join 只接受字符串序列
" ".join([1, 2, 3])
# ✅
" ".join(map(str, [1, 2, 3]))
# ✅ bytes 的 join（元素必须是 bytes）
b" ".join([b"a", b"b"])
map(str, ...)比[str(x) for x in ...]快，因为str是 C 函数，map的循环在 C 层。但如果里面是自己写的 Python 函数，列表推导反而更快 （见 21 章）。
70.5 竞赛常用操作速查¶
| 想做的事 | 写法 |
|---|---|
| 判回文 | s == s[::-1]（\(O(n)\)，C 层，见 72 章） |
| 找子串位置 | s.find(t)，找不到返回 \(-1\)；s.index(t) 找不到抛异常 |
| 找全部出现位置 | while (i := s.find(t, i)) >= 0: ...; i += 1 |
| 判前缀/后缀 | s.startswith(t) / s.endswith(t)，可传元组 |
| 统计不重叠出现次数 | s.count(t)（不含重叠！"aaa".count("aa") == 1） |
| 去重保序 | "".join(dict.fromkeys(s)) |
| 排序字符 | "".join(sorted(s))——判字母异位词的标准手法 |
| 循环移位 | s[k:] + s[:k] |
| 判 \(t\) 是 \(s\) 的循环移位 | len(s) == len(t) and t in s + s ← 非常好用 |
| 大小写无关比较 | s.casefold() == t.casefold() |
| 补齐到固定长度 | s.zfill(n)（补 0）、s.rjust(n, '0')、f"{x:05d}" |
| 反转每个单词 | " ".join(w[::-1] for w in s.split()) |
| 字符映射替换 | s.translate(str.maketrans("abc", "xyz"))（C 层，比循环快很多） |
s + s判循环移位是个高频技巧： \(t\) 是 \(s\) 的循环移位 \(\iff\) \(t\) 是 \(s+s\) 的子串（且长度相等）。 在 Python 里in是 C 实现，一行搞定；用 KMP 手写反而慢。
70.6 bytes vs str：决策表¶
| 判据 | 选 bytes |
选 str |
|---|---|---|
| 数据量 \(\ge 10^6\) 字符 | ✅ | ❌ |
| 需要逐字符比较（KMP、Manacher、Trie） | ✅ 明显更快 | |
| 需要原地修改 | ✅ 用 bytearray |
❌ 不可变 |
只用整串操作（find、count、in） |
都行 | 都行 |
| 需要格式化输出 | ✅ | |
| 有非 ASCII 字符 | ❌ | ✅ |
要当 dict 的键 |
都行 | 都行 |
混用时的三条规则：
b = s.encode() # str -> bytes
s = b.decode() # bytes -> str
b"abc" == "abc" # ❌ False！bytes 和 str 永远不相等
⚠️
bytes和str直接比较永远是False，而且不报错。 这是最阴险的 bug：读进来的是bytes，你拿"YES"去比， 永远走不进那个分支，程序照跑不误，只是答案全错。 写代码时保持全程一种类型，只在输出时转一次。
70.7 例题¶
BISHI10 小红的字符串修改（简单）¶
\(|s|, |t| \le 10^3\)，都由小写字母构成，\(|s| \le |t|\)。 每次可以把 \(s\) 的一个字母换成字母表中相邻的字母（
a和z也相邻）。 求最少替换多少次，使 \(s\) 成为 \(t\) 的连续子串。 题面见 BISHI10 原题（牛客）。 题解见solutions/BISHI10.py（已用官方样例验证）。
04 章 从「字符串基础」的角度讲过这题，这里从性能角度再看一遍。
算法：枚举 \(s\) 在 \(t\) 中的起始对齐位置（至多 \(|t|-|s|+1 \le 10^3\) 个）， 每个位置逐字符累加代价。字母表是环形的，所以单字符代价是
总量 \(10^3 \times 10^3 = 10^6\) 次基本运算。纯 Python 双重循环大约 1 秒， 时限「其他语言 2 秒」——能过但不宽裕。 把内层循环压到 C 层就稳了：
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 每一位的字母编号
# 枚举对齐起点；map(add, ...) 把「行首 + 列号」的下标计算放到 C 层，
# cost.__getitem__ 做查表，sum 做累加——内层一个 Python 字节码都没有
best = min(sum(map(cost.__getitem__, map(add, base, tc[off:off + n])))
for off in range(m - n + 1))
print(best)
这段代码值得逐层拆开看——它是「让循环消失」的教科书示范：
| 层 | 做的事 | 在哪跑 |
|---|---|---|
tc[off:off+n] |
取出 \(t\) 的对齐窗口 | C |
map(add, base, ...) |
逐位算出 行首 + 列号 = 一维下标 |
C |
map(cost.__getitem__, ...) |
逐个查代价表 | C |
sum(...) |
累加 | C |
min(... for off in ...) |
只有这一层是 Python 循环，\(10^3\) 次 | Python |
三个坑：
a和z相邻（字母表环形），代价是 \(\min(d, 26-d)\)， 不能直接用abs(ord(x) - ord(y))。样例 2（zzzzzz→xyzabc）就是在测这个：z→x是 2，z→y是 1，z→z是 0，z→a是 1，z→b是 2，z→c是 3， 合计 \(2+1+0+1+2+3 = 9\) ✓；- 这里的「子串」是连续子串（题面说的是「从开头和结尾各删若干字符」）， 不是子序列，所以只需枚举起点做定长对齐；
- 代价表扁平成一维（
cost[i*26+j]）而不是二维cost[i][j]， 这样__getitem__只查一次，配合map(add, ...)就能整条流水线走 C 层。
本题的通用套路：「两个序列逐位比较并求和」的循环， 在 Python 里可以用
sum(map(f, A, B))整个下沉到 C 层。 如果f是查表，就用table.__getitem__当f。
BISHI123 环形字符串跃迁（中等）¶
长度 \(n \le 10^5\) 的 01 环形字符串 \(S\)（\(S_n\) 的下一个是 \(S_1\)）。 光标在 \(S_i\) 时的跃迁规则：若 \(S_i\) 后方 \(m\) 个字符（不含 \(S_i\)）中存在
0， 就跳到其中最远的那个0；否则跳到 \(S_{i+1}\)。 \(q \le 10^5\) 次询问，每次给起点 \(t\) 和跃迁次数 \(k \le 10^{18}\)，问最终位置。 题面见 BISHI123 原题（牛客）。ℹ️ 本题的
solutions/题解文件尚未编写。下面的代码已由scripts/verify_docs.py用官方样例实测通过，并在本地用暴力对拍 （300 组随机小数据）与 \(n = q = 10^5\) 的极限数据验证过，但未在牛客提交。
这题只有一半是字符串题，值得先把两半拆开：
| 部分 | 属于 | 难点 |
|---|---|---|
求 nxt[i]（一次跃迁到哪） |
本章：环形字符串 + 滑动窗口 | 环形边界、"最远的 0" |
从 nxt 求 \(k\) 次跃迁的结果 |
45-倍增 / 函数图 | \(k \le 10^{18}\) |
第一半：把环拉直。 处理环形字符串的标准手法是 \(T = S + S\)—— 这样窗口 \([i+1, i+m]\) 就一定落在 \(T\) 内（因为 \(m \le n\)，\(i+m \le 2n-1\)）， 完全不用写取模的边界判断。
「最远的 0」= 窗口内下标最大的 0。所以只要预处理
一次线性扫描就能得到，然后
# [片段] 核心两行：p 是窗口右端往左找到的第一个 0
p = prevzero[i + m]
nxt[i] = p % n if p > i else (i + 1) % n # p <= i 说明窗口内没有 0
第二半：\(k \le 10^{18}\)。 每个位置只有一个后继，这是一张函数图
（每点出度为 1）。求「第 \(k\) 个后继」的标准做法是倍增：
预处理 up[b][i] = 从 \(i\) 跳 \(2^b\) 步到达的位置，然后按 \(k\) 的二进制位逐位跳。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2])
s = data[3] # bytes，长度 n
ZERO = 48 # ord('0')
# ---- 一、字符串预处理：环拉直成 T = s + s，求每个位置左侧最近的 0 ----
L = 2 * n
prevz = [-1] * L
last = -1
for j in range(L):
if s[j - n if j >= n else j] == ZERO: # 不真的拼出 s+s，省一次拷贝
last = j
prevz[j] = last
# ---- 二、一次跃迁：nxt[i] ----
nxt = [0] * n
for i in range(n):
p = prevz[i + m] # 窗口 [i+1, i+m] 内最靠右的 0
if p > i:
nxt[i] = p - n if p >= n else p # 手写取模，比 % 快
else:
nxt[i] = i + 1 if i + 1 < n else 0 # 窗口全是 1，走一步
# ---- 三、倍增：up[b][i] = 从 i 跳 2^b 步到哪 ----
LOG = 60 # 2^60 > 1e18
up = [nxt]
for _ in range(LOG - 1):
c = up[-1]
up.append([c[x] for x in c]) # ★ 列表推导，循环在 C 层
# ---- 四、逐位回答 ----
p = 4
out = []
for _ in range(q):
t = int(data[p]) - 1; k = int(data[p + 1]); p += 2
b = 0
while k:
if k & 1:
t = up[b][t]
k >>= 1
b += 1
out.append(t + 1)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
手动复核样例（\(n=8, m=3\)，\(S = \texttt{01110100}\)，0-indexed \(S = [0,1,1,1,0,1,0,0]\)）：
| \(i\)（0-idx） | 窗口（0-idx） | 窗口内的 0 | 最远的 | nxt[i] |
1-idx |
|---|---|---|---|---|---|
| 0 | 1,2,3 | 无 | — | 1 | \(1 \to 2\) |
| 1 | 2,3,4 | 4 | 4 | 4 | \(2 \to 5\) |
| 3 | 4,5,6 | 4,6 | 6 | 6 | \(4 \to 7\) |
| 6 | 7,8,9 | 7,8 | 8（即 0） | 0 | \(7 \to 1\) |
询问 1：\(1 \to 2 \to 5\)，输出 5 ✓ 询问 2：\(4 \to 7 \to 1 \to 2\)，输出 2 ✓
Python 现实性评估（\(n = q = 10^5\)，时限「其他语言 2 秒」）：
| 项 | 实测 |
|---|---|
prevz + nxt 预处理（\(3\times10^5\) 次循环） |
约 0.1 s |
| 倍增表 60 层 × \(10^5\) = \(6\times10^6\) 次列表推导 | 约 0.4 s |
| \(10^5\) 次询问 × 最多 60 位 | 约 0.3 s |
| 总计 | 约 0.8 s ✅ |
四个坑：
- 「最远的 0」是下标最大的，不是最小的。读题时很容易看成「最近的」， 两者答案完全不同；
- 不要真的拼出
s + s：s[j - n if j >= n else j]一个条件表达式就够了， 省掉一次 \(10^5\) 字节的拷贝（虽然这点开销不大，但这个「虚拟拼接」的思路 在 \(n = 10^6\) 时就重要了）； up.append([c[x] for x in c])这一行是整个倍增的性能关键。 写成for i in range(n): up[b][i] = up[b-1][up[b-1][i]]要慢 3 倍以上—— 列表推导 + 直接迭代c的元素，把 \(6\times10^6\) 次循环压到了 C 层；- \(k\) 可以等于 0（题面写的是 \(0 \le k\)），此时直接输出起点。
上面的
while k:天然处理了这种情况。
更快的做法：函数图上还有 \(O(n+q)\) 的写法—— 先找出所有环，把挂在环上的树离线 DFS 一遍， 用「根到当前点的路径栈」\(O(1)\) 回答「\(k\) 步以内还在树上」的询问， 超出树高的部分在环上取模。本地实测 0.2 s（比倍增快 4 倍）， 但代码长 3 倍。倍增版已经能过，就不必上这个。 函数图的结构分析见 38-并查集 的 BISHI98。
70.8 本章速查¶
| 要点 | 结论 |
|---|---|
| 竞赛默认表示 | bytes（sys.stdin.buffer.read().split()） |
b[i] |
是 int，不是字符！要 b[i] == ord('#') |
b[i:j] |
是 bytes |
bytes == str |
永远 False 且不报错——最阴险的 bug |
str 可变吗 |
❌ 不可变，s[i] = 'x' 直接报错 |
| 循环拼接 | \(O(n^2)\)，一律改 "".join(...) |
| 逐字符改 | 用 bytearray（\(O(1)\) 单点改 + 支持切片赋值） |
| 切片 | 是复制不是视图，\(O(r-l)\)；循环里切大片 = 平方级 |
| 构造带分隔符的串 | bytearray + 切片步长赋值（t[1::2] = s） |
split() vs split(' ') |
一律用无参版，顺带处理 \r\n |
join |
元素必须是 str（或全 bytes），配 map(str, ...) |
| ASCII | '0'=48，'A'=65，'a'=97 |
| 翻转大小写 | ch ^ 32 |
| 26 字母计数 | 定长 list 比 Counter 快 2–3 倍 |
| 只数一个字符 | s.count(x)（纯 C） |
count 重叠吗 |
❌ 不含重叠："aaa".count("aa") == 1 |
| 判回文 | s == s[::-1]（C 层 \(O(n)\)） |
| 判循环移位 | len(s)==len(t) and t in s+s |
| 判字母异位词 | sorted(s) == sorted(t) |
| 批量字符替换 | str.translate + str.maketrans（C 层） |
| 环形字符串 | 拉直成 \(S+S\)，或用条件表达式虚拟拼接 |
| 「两序列逐位算再求和」 | sum(map(f, A, B))，全程 C 层 |
| 症状 → 原因 |
|---|
| 字符串操作莫名超时 |
| 比较永远不相等 |
TypeError: 'str' object does not support item assignment |
用 ord 比较 bytes 元素报错 |
多组数据里 split(' ') 出现空串 |