字符串 (string) 是字符组成的有限序列, 一般记为 `s = a_0 a_1 cdots a_(n-1)`, `quad n ge 0`. 字符数目 `n` 称为串的长度. 长度为 0 的串称为空串 (null string), 记为 `epsi`. 若 `s` 为非空串, 我们称 `i` 是字符 `a_i` 在串中的下标. 字符串的下标是从 0 开始的. 串中连续 `k ge 0` 个字符组成的子序列称为该串的子串 (substring). 用 a[i:j] 表示 `a_i, cdots, a_(j-1)` 所组成的子串, 称为字符串的一个切片. 注意切片是左闭右开的. 特别 `i = j` 时上述切片是一个空串.

字符串的存储

定长顺序存储 (数组)

字符串的定长顺序存储 在字符串尾追加空字符 '\0' 作为串结束标识. 可以增加一变量 len 表示字符串长. 定长有中序存储的优点是方便; 缺点是连接, 插入, 置换等操作可能使字符串超出给定长度. 

struct StaticString:
	char str[N+1]
	int len

定长顺序存储下字符串的连接 将两字符串 this 与 str 连接的结果保存在 this 中. 超出部分被截断. 

StaticString.strcat(str):
	i = 0
	while this[i] != '\0':
		++i
	j = 0
	while str[j] != '\0' and i < N:
		this[i++] = str[j++]
	this[i] = '\0'

堆分配存储 (动态数组)

也是字符串最常用的存储方式. 与定长存储相比, 当字符串长度超过当前容量时, 可以重新分配内存以适应新的长度. 

struct HeapString
	char *str
	int len
	int cap # capacity

堆分配串的赋值 使用所谓 "copy and swap idiom". 

# str 以传值形式传入, 在函数退出时被销毁
HeapString.assign(str):
	swap(this.str, str.str)
	this.len = str.len
	this.cap = str.cap

块链存储 (链表)

串的块链存储 使用一单链表存储字符串, 每个链表结点含有 CHUNK_SIZE 个字符. 最后一个块链通常未必装满, 可在串尾追加空字符. 串的链式存储在连接等操作上有一定方便之处, 但总的来说占用空间大且操作复杂. 

CHUNK_SIZE 80
struct Chunk:
	char str[CHUNK_SIZE]
	Chunk *next

struct ChunkString:
	Chunk *head, *tail
	int len

模式匹配算法*

模式匹配即查找子串的算法. 假定模式串 p 非空, 在主串 s 中查找 p 出现的所有下标. 也可以是找出所有不重叠的子串 p 的下标.

朴素匹配

朴素匹配算法 依次将 p[0] 和主串的下标 0, 1, 2, ... 对齐进行串的匹配, 直到匹配成功或尝试过所有偏移量而失败为止. 时间复杂度为 O(s.len*p.len). 

naive_match(s, p):
	i = j = 0
	while i < s.len:
		if s[i] != p[j]:	# 失败
			i -= j-1		# i 回退, 注意 j == 0 时 i 实际上在变大
			j = 0			# j 清零
		elif j == p.len-1:	# 成功
			print(i-j)
			i -= j-1		# 要求子串不重叠时, 这里写 ++i
			j = 0
		else:
			++i, ++j

KMP 算法

KMP (Knuth-Morris-Pratt) 算法 朴素匹配算法中, 遇到匹配失败 (失配) 时, 指针 i 需要回退. 这是可以避免的. 事实上根据模式串自己与自己匹配时的信息, 可以计算出失配时模式串应当向右滑动的距离.
设主串为 s, 模式串为 p, 当发生失配 s[i] != p[j] 时, 假设 s[i] 应继续与 p[k] 相比较, k < j. 则必有 p[0:k] == s[i-k:i] 由失配前已经完成的匹配有 p[j-k:j] == s[i-k:i] 两式比较得 p[0:k] == p[j-k:j] 可以看出, 当 p[j] 与主串对应字符发生失配时, 下一个参与比较的字符 p[k] 仅由模式串自身决定, 而与主串无关. 反之, 若模式串中存在满足上式的 k, j, 则当 p[j] 与主串发生失配时, 只需将模式串向右滑动, 以 p[k] 取代 p[j] 的位置. 这时 p[0:k] 已经与主串的对应字符匹配, 只需从 p[k] 开始继续匹配即可. 显然为减少工作量, k 值越大越好.
定义 next[j] 为当 p[j] 与主串发生失配时, 模式串中下一个参与比较的字符下标. 特别 j == 0 时, 表示模式串的首个字符即发生失配. 这时简单将模式串向右移动一个字符即可, 换言之, 应当将下标 -1 的假想字符与主串的原位置对齐. 但注意这种情形下, 应将 i, j 同时增 1, 从下标 0 开始匹配. 由上述讨论, `"next"[j] = { -1, if j = 0; max{k | k lt j and p[0:k] = p[j-k:j]}, otherwise :}` 在已知 next[0:p.len] 的情况下, 匹配算法的草稿如下. 

kmp_match_draft(s, p):
	get_next(p)
	i = j = 0
	while i < s.len:
		if j != -1 and s[i] != p[j]: # 失败
			j = next[j]
		elif j == p.len-1:			 # 成功
			print(i-j)
			j = next[j]
		else:
			++i, ++j

我们看到, 失配时指针 i 已经不回退, 而 j 也不至于回退至 0 了. 注意到失败和成功时指针 i 均不变, 所以无需反复进行 i < s.len 的判断. 我们可以将算法的 if 改成 while, elif 改成 if, 得到最终版本: 

kmp_match(s, p):
	get_next(p)
	i = j = 0
	while i < s.len:
		while j != -1 and s[i] != p[j]:	# 失败
			j = next[j]
		if j == p.len-1:				# 成功
			print(i-j)
			j = next[j]
		else:
			++i, ++j

我们来求向量 next. 由定义, next[0] == -1. 现在设 next[j] == k, 来求 next[j+1]. 当 j > 0, 由 next[j] == k, 存在 k < j, 使得 p[0:k] == p[j-k:j], 且不存在 k' > k 满足上式. 考虑 p[j], p[k] 的关系:
情况一, 若 p[j] == p[k], 则 p[0:k+1] == p[j-k:j+1], 且不存在 k' > k 满足上式. 即 next[j+1] == k+1.
情况二, 若 p[j] != p[k], 可以看成模式串与自己匹配过程中出现失配, 为了化为情况一, 应当寻找下一合适的 p[k1] 与 p[j] 比较, 由 KMP 匹配过程的讨论知道, 这个 k1 = next[k]. 若 p[k1] == p[j], 即化为情况一, 否则继续令 k2 = next[k1]. 由于 next 函数严格单调减的性质, 我们总能化为情况一, 或者最终得到一个 kn == -1. 这时无法找到一个 0 < k < j 使得 p[0:k+1] == p[j-k:j+1], 因此 next[j+1] = 0 (== kn+1). 

get_next(p):
	j, k = 0, -1
	next[j] = k
	while j < p.len-1:
		while k != -1 and p[j] != p[k]:
			k = next[k]
		next[++j] = ++k

考虑一种特殊情况: next[j] == k, 且 p[j] == p[k]. 若这时发生失配 s[i] != p[j], 按 KMP 算法, 应当以 p[k] 与 s[i] 比较, 但是其结果必然不相等! 针对这种情况, 我们可以直接取 next[j] = next[k], 以减少不必要的比较. 算法最终如下: 

get_next_improved(p):
	j, k = 0, -1
	next[j] = k
	while j < p.len-1:
		while k != -1 and p[j] != p[k]:
			k = next[k]
		if p[++j] == p[++k]:
			next[j] = next[k]
		else:
			next[j] = k

当我们需要找出所有 (可重叠的) 子串 p 的位置时, 应采用 get_next; 当我们要找出所有不重叠的子串的位置时, 则用 get_next_improved.

由于指针 i 不回溯, 所以匹配的时间复杂度为 O(s.len). 另外, 预处理的过程就是模式串与自己匹配的过程, 时间复杂度为 O(p.len). 总时间复杂度为两项之和.

Boyer-Moore 算法

Boyer-Moore 算法 [来自 知乎@帅地, OI Wiki] 优于 KMP, 这是文本编辑器中查找功能最常用的算法.

编辑距离算法

    编辑距离算法 [来自 CSDN@xcxy2015] 编辑距离是指, 从一个串变为另一个串所需的增、删、改的最少次数. 比如从 hurt 变为 heart 的编辑方案一共两步:
  1. 把 u 换成 e;
  2. 在刚才的 e 后面插入 a.
    3. 算法列表如下: 
        h e a r t
  0 1 2 3 4 5
h 1
u 2
r 3
t 4
    逐行填写, 每个格子的值 = 1 + min(左上格子的值 - s, 上方格子的值, 左方格子的值). 若当前比较的两个字母相等, 则 s = 1, 否则 s = 0. 
        h e a r t
  0 1 2 3 4 5
h 1 0 1 2 3 4
u 2 1 1 2 3 4
r 3 2 2 2 2 3
t 4 3 3 3 3 2
    个人理解: 这是一个动态规划算法, 左方、上方和左上三个格子分别表示增、删、改三种选择. 如表中的 3 行 4 列, 比较串 hur 和 hear. 要将 hur 变为 hear, 方案有三:
  1. 「增」的方案. 先把 hur 变为 hea, 再增加一个字母 r 得到目标 hear. 编辑距离为 2 + 1.
  2. 「删」的方案. 先把 hur 删去一个字母变为 hu, 再把 hu 变为 hear. 编辑距离为 1 + 3.
  3. 「改」的方案. 先把 hur 的最后一个字母改成和 hear 的最后一个字母相同 (它们已经相同, 因此代价为 0), 再把 hur 的前面几个字母变成和 hear 的前面几个字母相同 (即把 hu 变为 hea). 编辑距离为 0 + 2.
    4. 从三个方案中取最小的即可.

LZ77 压缩算法

    LZ77 压缩算法 是基于字典的压缩算法, 也是很多现代压缩算法 (包括 zip) 的基础.
  1. 将待编码数据看作字符串, 以一个固定宽度的窗口在其中滑动, 窗口右端 win[k:] 是待编码区, 左端 win[0:k] 是已编码区.
  2. 编码时, 从待编码区的第一个字符开始, 在已编码区查找最大匹配字符串: 即寻找最大的 length, 使得 win[k-offset:k-offset+length] == win[k:k+length].
  3. 如果匹配成功, 输出三元组 (offset, length, null), 并将窗口向后滑动 length个字符; 否则输出 (0, 0, win[k]), 并将窗口向后滑动 1 个字符.

压缩

解压缩