字符串

(字符)串 (string) 是字符组成的有限序列, 一般记为 `s = a_1 a_2 cdots a_n`, `quad n ge 0`. 字符数目 `n` 称为串的长度. 长度为 0 的串称为空串 (null string), 记为 `epsi`. 串中连续 `k` 个字符组成的子序列称为该串的子串 (substring) (`k ge 0`). 若 `s` 为非空串, 则字符 `a_i` 在串中的下标定义为 `i-1`. 于是字符串的下标是从 0 开始的. 用 str[i..j] 表示下标 i, j 间的字符 (含两端) 所组成的子串. 特别, i == j+1 时表示空串.

字符串的存储

定长顺序存储 (数组)

字符串的定长顺序存储 在字符串尾追加空字符 '\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 (Knuth-Morris-Pratt) 算法 朴素匹配算法中, 遇到匹配失败 (失配) 时, 指针 i 需要回退. 这是可以避免的. 事实上根据模式串自己与自己匹配时的信息, 可以计算出失配时模式串应当向右滑动的距离.
设主串为 s, 模式串为 p, 当发生失配 s[i] != p[j] 时, 假设 s[i] 应继续与 p[k] 相比较, k < j. 则必有 p[0..k-1] == s[i-k..i-1] 由失配前已经完成的匹配有 p[j-k..j-1] == s[i-k..i-1] 两式比较得 p[0..k-1] == p[j-k..j-1] 可以看出, 当 p[j] 与主串对应字符发生失配时, 下一个参与比较的字符 p[k] 仅由模式串自身决定, 而与主串无关. 反之, 若模式串中存在满足上式的 k, j, 则当 p[j] 与主串发生失配时, 只需将模式串向右滑动, 以 p[k] 取代 p[j] 的位置. 这时 p[0..k-1] 已经与主串的对应字符匹配, 只需从 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-1] = p[j-k..j-1]}, otherwise :}` 在已知 next[0..p.len-1] 的情况下, 匹配算法的草稿如下.

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-1] == p[j-k..j-1], 且不存在 k' > k 满足上式. 考虑 p[j], p[k] 的关系:
情况一, 若 p[j] == p[k], 则 p[0..k] == p[j-k..j], 且不存在 k' > k 满足上式. 即 next[j+1] == k+1.
情况二, 若 p[j] != p[k], 可以看成模式串与自己匹配过程中出现失配, 为了化为情况一, 应当寻找下一合适的 p[k₁] 与 p[j] 比较, 由 KMP 匹配过程的讨论知道, 这个 k₁ = next[k]. 若 p[k₁] == p[j], 即化为情况一, 否则继续令 k₂ = next[k₁]. 由于 next 函数严格单调减的性质, 我们总能化为情况一, 或者最终得到一个 k_n == -1. 这时无法找到一个 0 < k < j 使得 p[0..k] == p[j-k..j], 因此 next[j+1] = 0 (== k_n+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 算法 [来自知乎@帅地] 文本编辑器中查找功能最常用的算法.

编辑距离算法

CSDN@xcxy2015

把 u 换成 e;
在刚才的 e 后面插入 a.

    h e a r t
  0 1 2 3 4 5
h 1
u 2
r 3
t 4

    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

「增」的方案. 先把 hur 变为 hea, 再增加一个字母 r 得到目标 hear. 编辑距离为 2 + 1.
「删」的方案. 先把 hur 删去一个字母变为 hu, 再把 hu 变为 hear. 编辑距离为 1 + 3.
「改」的方案. 先把 hur 的最后一个字母改成和 hear 的最后一个字母相同 (它们已经相同, 因此代价为 0), 再把 hur 的前面几个字母变成和 hear 的前面几个字母相同 (即把 hu 变为 hea). 编辑距离为 0 + 2.

def edit_distance(s1, s2):
    len1 = len(s1)
    len2 = len(s2)
    arr = [
        [j if i == 0 else i if j == 0 else 0 for j in range(len2+1)]
        for i in range(len1+1)
    ]
    for i in range(len1):
        for j in range(len2):
            top_left_value = arr[i][j] - (1 if s1[i] == s2[j] else 0)
            top_value = arr[i][j+1]
            left_value = arr[i+1][j]
            arr[i+1][j+1] = 1 + min(top_left_value, top_value, left_value)
    return arr[-1][-1]

def similarity(s1, s2):
    d = edit_distance(s1, s2)
    return 1 - d / max(len(s1), len(s2), 1) # 防止分母为零

print(similarity('hurt', 'heart')) # 1 - 2/5 = 0.6