第6章字符串与文本处理理论

本章导读

字符串是计算机科学中最基础的数据类型之一，文本处理是现代软件系统的核心功能。本章从形式语言理论角度深入分析字符串的数学基础，包括字符串ADT规范、模式匹配算法（KMP、Boyer-Moore）、后缀数组理论，以及Unicode编码的数学模型。

学习目标

完成本章学习后，读者将能够：

掌握字符串的形式化定义与ADT规范
理解模式匹配算法的理论基础与复杂度分析
掌握KMP算法的失败函数计算
理解后缀数组的构造与应用
掌握Unicode编码的数学模型

6.1 字符串的形式化理论

6.1.1 字符串的数学定义

定义 6.1（字母表） 字母表 $\Sigma$ 是一个有限非空符号集合。例如：

$\Sigma_{ASCII} = {0, 1, \ldots, 127}$
$\Sigma_{Unicode} = {0, 1, \ldots, 1114111}$
$\Sigma_{binary} = {0, 1}$

定义 6.2（字符串） 字符串是字母表 $\Sigma$ 上符号的有限序列。$\Sigma^*$ 表示 $\Sigma$ 上所有字符串的集合，包括空串 $\varepsilon$。

$$\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n$$

其中 $\Sigma^n$ 是长度为 $n$ 的所有字符串的集合。

定义 6.3（字符串长度） 字符串 $s$ 的长度 $|s|$ 定义为其中符号的个数。$|\varepsilon| = 0$。

定义 6.4（字符串连接） 字符串 $s$ 和 $t$ 的连接 $s \cdot t$（或简写为 $st$）定义为：

$$s \cdot t = s[0]s[1]\ldots s[|s|-1]t[0]t[1]\ldots t[|t|-1]$$

定理 6.1（字符串连接的性质） 字符串连接满足：

封闭性：$s, t \in \Sigma^* \Rightarrow st \in \Sigma^*$
结合律：$(st)u = s(tu)$
单位元：$s\varepsilon = \varepsilon s = s$
长度可加性：$|st| = |s| + |t|$

证明：由定义直接验证。结合律：$(st)u$ 和 $s(tu)$ 都等于 $s[0]\ldots s[|s|-1]t[0]\ldots t[|t|-1]u[0]\ldots u[|u|-1]$。∎

定义 6.5（子串） 字符串 $t$ 是 $s$ 的子串，当且仅当存在 $u, v \in \Sigma^*$ 使得 $s = utv$。

定义 6.6（前缀与后缀）

前缀：$t$ 是 $s$ 的前缀，当且仅当存在 $u$ 使得 $s = tu$，记作 $t \sqsubseteq s$
后缀：$t$ 是 $s$ 的后缀，当且仅当存在 $u$ 使得 $s = ut$，记作 $t \sqsupseteq s$

6.1.2 字符串ADT规范

ADT 6.1（String）

ADT String
  Types: String
  
  Operations:
    empty: → String
    length: String → ℕ
    charAt: String × ℕ → Symbol
    concat: String × String → String
    substring: String × ℕ × ℕ → String
    indexOf: String × String → ℕ ∪ {-1}
    equals: String × String → Boolean
    compare: String × String → {-1, 0, 1}
  
  Axioms:
    ∀s, t: String, ∀i, j: ℕ
    (A1) length(empty) = 0
    (A2) length(concat(s, t)) = length(s) + length(t)
    (A3) i < length(s) → charAt(s, i) = s[i]
    (A4) i ≥ length(s) → charAt(s, i) = error
    (A5) substring(s, i, j) = s[i]s[i+1]...s[j-1]  (当 0 ≤ i ≤ j ≤ length(s))
    (A6) indexOf(s, t) = min{i : substring(s, i, i+length(t)) = t} ∪ {-1}
    (A7) equals(s, t) = (∀i < length(s), charAt(s, i) = charAt(t, i)) ∧ length(s) = length(t)
    (A8) compare(s, t) = -1 if s < t (lexicographic)
                     = 0  if s = t
                     = 1  if s > t

定理 6.2（字符串ADT一致性） 字符串ADT的公理系统是一致的。

证明：构造数组模型。设字符串为字符数组 $s[0..n-1]$。

$empty = []$
$length(s) = n$
$charAt(s, i) = s[i]$
$concat(s, t) = s + t$（数组连接）
$substring(s, i, j) = s[i:j]$

可直接验证所有公理成立。∎

6.1.3 字典序与排序

定义 6.7（字典序） 字符串的字典序定义为：

$$s < t \iff \begin{cases} s \sqsubset t, \text{或} \ s = uv, t = uw, v[0] < w[0] \end{cases}$$

其中 $s \sqsubset t$ 表示 $s$ 是 $t$ 的真前缀。

定理 6.3（字典序的全序性） 字典序是 $\Sigma^*$ 上的全序关系。

证明：需要证明自反性、反对称性、传递性和完全性。

自反性：$s = s$，故 $s \leq s$
反对称性：若 $s \leq t$ 且 $t \leq s$，则 $s = t$
传递性：若 $s \leq t$ 且 $t \leq u$，则 $s \leq u$
完全性：对于任意 $s, t$，要么 $s \leq t$，要么 $t \leq s$

完全性证明：设 $s, t$ 的最长公共前缀为 $p$，则 $s = pv$，$t = pw$。若 $v = \varepsilon$ 或 $w = \varepsilon$，则一个是另一个的前缀。否则比较 $v[0]$ 和 $w[0]$。∎

6.2 模式匹配算法理论

6.2.1 问题定义

定义 6.8（模式匹配问题） 给定文本 $T[0..n-1]$ 和模式 $P[0..m-1]$，找出 $P$ 在 $T$ 中所有出现的位置。

定义 6.9（匹配） $P$ 在位置 $i$ 与 $T$ 匹配，当且仅当 $T[i..i+m-1] = P$。

定理 6.10（朴素算法复杂度） 朴素模式匹配算法的最坏时间复杂度为 $O(nm)$。

证明：考虑 $T = a^n$ 和 $P = a^{m-1}b$。每次匹配需要比较 $m$ 个字符，共 $n-m+1$ 次尝试，总比较次数为 $(n-m+1) \cdot m = O(nm)$。∎

6.2.2 KMP算法

定义 6.10（失败函数） 失败函数 $\pi: {0, \ldots, m-1} \to {0, \ldots, m-1}$ 定义为：

$$\pi[q] = \max{k : k < q \land P[0..k-1] = P[q-k..q-1]}$$

即 $\pi[q]$ 是 $P[0..q-1]$ 的最长真前缀同时也是其后缀的长度。

定理 6.4（失败函数计算） 失败函数可在 $O(m)$ 时间内计算。

证明：使用递推计算。设已计算 $\pi[0..q-1]$，计算 $\pi[q]$：

设 $k = \pi[q-1]$
若 $P[k] = P[q-1]$，则 $\pi[q] = k + 1$
否则，递归查找 $k = \pi[k]$ 直到 $k = 0$ 或 $P[k] = P[q-1]$

每次迭代 $k$ 至少减1，而 $k$ 最多增加 $m$ 次，因此总时间为 $O(m)$。∎

定理 6.5（KMP算法复杂度） KMP算法的时间复杂度为 $O(n + m)$。

证明：分析字符比较次数。设 $i$ 为文本指针，$j$ 为模式指针。

每次成功匹配：$i$ 增加，$j$ 增加
每次失败：$j$ 减少到 $\pi[j]$

$j$ 的总增加量不超过 $n$，总减少量不超过 $m$，因此总比较次数为 $O(n + m)$。∎

6.2.3 KMP算法实现

python

from typing import List, Iterator

def compute_prefix_function(pattern: str) -> List[int]:
    """
    计算KMP失败函数（前缀函数）
    
    时间复杂度：O(m)
    空间复杂度：O(m)
    
    pi[q] = P[0..q-1]的最长真前缀同时也是后缀的长度
    """
    m = len(pattern)
    pi = [0] * m
    k = 0
    
    for q in range(1, m):
        while k > 0 and pattern[k] != pattern[q]:
            k = pi[k - 1]
        
        if pattern[k] == pattern[q]:
            k += 1
        
        pi[q] = k
    
    return pi


def kmp_search(text: str, pattern: str) -> Iterator[int]:
    """
    KMP模式匹配算法
    
    时间复杂度：O(n + m)
    空间复杂度：O(m)
    
    Args:
        text: 文本字符串
        pattern: 模式字符串
    
    Yields:
        匹配的起始位置
    """
    n, m = len(text), len(pattern)
    
    if m == 0:
        yield from range(n + 1)
        return
    
    if m > n:
        return
    
    pi = compute_prefix_function(pattern)
    q = 0
    
    for i in range(n):
        while q > 0 and pattern[q] != text[i]:
            q = pi[q - 1]
        
        if pattern[q] == text[i]:
            q += 1
        
        if q == m:
            yield i - m + 1
            q = pi[q - 1]


def kmp_count(text: str, pattern: str) -> int:
    """计算模式出现次数"""
    return sum(1 for _ in kmp_search(text, pattern))


def kmp_find_all(text: str, pattern: str) -> List[int]:
    """找出所有匹配位置"""
    return list(kmp_search(text, pattern))


class KMPMatcher:
    """
    KMP匹配器（预编译模式）
    
    适用于多次匹配同一模式的场景
    """
    
    def __init__(self, pattern: str):
        self._pattern = pattern
        self._pi = compute_prefix_function(pattern)
    
    def search(self, text: str) -> Iterator[int]:
        """在文本中搜索模式"""
        n = len(text)
        m = len(self._pattern)
        
        if m == 0:
            yield from range(n + 1)
            return
        
        if m > n:
            return
        
        q = 0
        for i in range(n):
            while q > 0 and self._pattern[q] != text[i]:
                q = self._pi[q - 1]
            
            if self._pattern[q] == text[i]:
                q += 1
            
            if q == m:
                yield i - m + 1
                q = self._pi[q - 1]
    
    @property
    def pattern(self) -> str:
        return self._pattern
    
    @property
    def prefix_function(self) -> List[int]:
        return self._pi.copy()


def demonstrate_kmp():
    """演示KMP算法"""
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    
    print(f"文本: {text}")
    print(f"模式: {pattern}")
    
    pi = compute_prefix_function(pattern)
    print(f"\n前缀函数: {pi}")
    
    positions = kmp_find_all(text, pattern)
    print(f"\n匹配位置: {positions}")
    
    for pos in positions:
        print(f"  位置 {pos}: {text[pos:pos+len(pattern)]}")


if __name__ == '__main__':
    demonstrate_kmp()

6.2.4 Boyer-Moore算法

定义 6.11（坏字符规则） 当匹配失败在位置 $i$ 时，若 $T[i]$ 不在 $P$ 中，则将 $P$ 右移 $i + 1$ 位；否则将 $P$ 右移使 $P$ 中最右的 $T[i]$ 与 $T[i]$ 对齐。

定义 6.12（好后缀规则） 当匹配失败时，利用已匹配的后缀信息，将 $P$ 右移到下一个可能匹配的位置。

定理 6.6（Boyer-Moore复杂度） Boyer-Moore算法的最坏时间复杂度为 $O(nm)$，但在实践中通常为 $O(n/m)$。

证明：最坏情况出现在 $T = a^n$ 和 $P = ba^{m-1}$，每次只移动1位。但实际文本中，坏字符规则通常使模式大幅跳跃。∎

python

from typing import List, Dict

class BoyerMooreMatcher:
    """
    Boyer-Moore字符串匹配算法
    
    时间复杂度：
    - 最坏：O(nm)
    - 平均：O(n/m)
    - 预处理：O(m + |Σ|)
    """
    
    def __init__(self, pattern: str, alphabet_size: int = 256):
        self._pattern = pattern
        self._m = len(pattern)
        self._alphabet_size = alphabet_size
        
        self._bad_char = self._compute_bad_char_table()
        self._good_suffix = self._compute_good_suffix_table()
    
    def _compute_bad_char_table(self) -> List[int]:
        """计算坏字符跳转表"""
        table = [self._m] * self._alphabet_size
        
        for i in range(self._m - 1):
            table[ord(self._pattern[i])] = self._m - 1 - i
        
        return table
    
    def _compute_good_suffix_table(self) -> List[int]:
        """计算好后缀跳转表"""
        m = self._m
        table = [0] * (m + 1)
        
        suffix = [0] * (m + 1)
        
        suffix[m - 1] = m
        g = m - 1
        f = 0
        
        for i in range(m - 2, -1, -1):
            if i > g and suffix[i + m - 1 - f] < i - g:
                suffix[i] = suffix[i + m - 1 - f]
            else:
                g = min(g, i)
                f = i
                while g >= 0 and self._pattern[g] == self._pattern[g + m - 1 - f]:
                    g -= 1
                suffix[i] = f - g
        
        for i in range(m):
            table[i] = m
        
        j = 0
        for i in range(m - 1, -1, -1):
            if suffix[i] == i + 1:
                while j < m - 1 - i:
                    if table[j] == m:
                        table[j] = m - 1 - i
                    j += 1
        
        for i in range(m - 1):
            table[m - 1 - suffix[i]] = m - 1 - i
        
        return table
    
    def search(self, text: str) -> List[int]:
        """搜索所有匹配位置"""
        n = len(text)
        m = self._m
        
        if m == 0:
            return list(range(n + 1))
        
        if m > n:
            return []
        
        result = []
        s = 0
        
        while s <= n - m:
            j = m - 1
            
            while j >= 0 and self._pattern[j] == text[s + j]:
                j -= 1
            
            if j < 0:
                result.append(s)
                s += self._good_suffix[0]
            else:
                bad_char_shift = self._bad_char[ord(text[s + j])] - (m - 1 - j)
                good_suffix_shift = self._good_suffix[j + 1]
                s += max(bad_char_shift, good_suffix_shift)
        
        return result

6.3 后缀数组理论

6.3.1 后缀数组的定义

定义 6.13（后缀） 字符串 $S$ 的第 $i$ 个后缀定义为 $S[i..n-1]$，记作 $S_i$。

定义 6.14（后缀数组） 后缀数组 $SA$ 是 $[0, n-1]$ 的一个排列，使得 $S_{SA[0]} < S_{SA[1]} < \ldots < S_{SA[n-1]}$（字典序）。

定义 6.15（排名数组） 排名数组 $Rank$ 是后缀数组的逆：$Rank[i]$ 表示后缀 $S_i$ 在所有后缀中的排名。

定理 6.7（后缀数组性质）

$SA[Rank[i]] = i$
$Rank[SA[i]] = i$

6.3.2 LCP数组

定义 6.16（LCP数组） LCP（最长公共前缀）数组 $LCP[i]$ 表示后缀 $S_{SA[i-1]}$ 和 $S_{SA[i]}$ 的最长公共前缀长度。

定理 6.8（LCP与后缀匹配） 后缀 $S_i$ 和 $S_j$（$Rank[i] < Rank[j]$）的最长公共前缀长度为：

$$LCP(S_i, S_j) = \min_{k=Rank[i]+1}^{Rank[j]} LCP[k]$$

定理 6.9（Kasai算法） LCP数组可在 $O(n)$ 时间内计算。

证明：Kasai算法利用后缀之间的关系。若 $LCP(S_i, S_j) = h > 0$，则 $LCP(S_{i+1}, S_{j+1}) \geq h - 1$。通过维护当前LCP值，每个字符最多被比较一次。∎

6.3.3 后缀数组实现

python

from typing import List, Tuple

class SuffixArray:
    """
    后缀数组实现
    
    时间复杂度：
    - 构造：O(n log n)
    - LCP计算：O(n)
    
    空间复杂度：O(n)
    """
    
    def __init__(self, text: str):
        self._text = text
        self._n = len(text)
        self._sa = self._build_suffix_array()
        self._rank = self._build_rank()
        self._lcp = self._build_lcp()
    
    def _build_suffix_array(self) -> List[int]:
        """构造后缀数组（O(n log n)）"""
        n = self._n
        text = self._text
        
        sa = list(range(n))
        rank = [ord(text[i]) for i in range(n)]
        tmp = [0] * n
        
        k = 1
        while k < n:
            def sort_key(i):
                return (rank[i], rank[i + k] if i + k < n else -1)
            
            sa.sort(key=sort_key)
            
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i - 1]] + (sort_key(sa[i - 1]) != sort_key(sa[i]))
            
            rank = tmp[:]
            k *= 2
            
            if rank[sa[n - 1]] == n - 1:
                break
        
        return sa
    
    def _build_rank(self) -> List[int]:
        """构建排名数组"""
        rank = [0] * self._n
        for i, sa_i in enumerate(self._sa):
            rank[sa_i] = i
        return rank
    
    def _build_lcp(self) -> List[int]:
        """Kasai算法计算LCP数组（O(n)）"""
        n = self._n
        text = self._text
        sa = self._sa
        rank = self._rank
        
        lcp = [0] * n
        h = 0
        
        for i in range(n):
            if rank[i] > 0:
                j = sa[rank[i] - 1]
                
                while i + h < n and j + h < n and text[i + h] == text[j + h]:
                    h += 1
                
                lcp[rank[i]] = h
                
                if h > 0:
                    h -= 1
        
        return lcp
    
    @property
    def sa(self) -> List[int]:
        return self._sa.copy()
    
    @property
    def rank(self) -> List[int]:
        return self._rank.copy()
    
    @property
    def lcp(self) -> List[int]:
        return self._lcp.copy()
    
    def count_occurrences(self, pattern: str) -> int:
        """统计模式出现次数（O(m log n)）"""
        n, m = self._n, len(pattern)
        text = self._text
        sa = self._sa
        
        if m == 0:
            return n + 1
        if m > n:
            return 0
        
        def compare_suffix(idx: int) -> int:
            suffix = text[idx:idx + m]
            if suffix < pattern:
                return -1
            elif suffix > pattern:
                return 1
            return 0
        
        left, right = 0, n
        while left < right:
            mid = (left + right) // 2
            if compare_suffix(sa[mid]) < 0:
                left = mid + 1
            else:
                right = mid
        
        start = left
        
        right = n
        while left < right:
            mid = (left + right) // 2
            if compare_suffix(sa[mid]) <= 0:
                left = mid + 1
            else:
                right = mid
        
        return left - start
    
    def find_all_occurrences(self, pattern: str) -> List[int]:
        """找出模式所有出现位置"""
        n, m = self._n, len(pattern)
        text = self._text
        sa = self._sa
        
        if m == 0:
            return list(range(n + 1))
        if m > n:
            return []
        
        def compare_suffix(idx: int) -> int:
            suffix = text[idx:idx + m]
            if suffix < pattern:
                return -1
            elif suffix > pattern:
                return 1
            return 0
        
        left, right = 0, n
        while left < right:
            mid = (left + right) // 2
            if compare_suffix(sa[mid]) < 0:
                left = mid + 1
            else:
                right = mid
        
        start = left
        
        right = n
        while left < right:
            mid = (left + right) // 2
            if compare_suffix(sa[mid]) <= 0:
                left = mid + 1
            else:
                right = mid
        
        return sorted(sa[start:left])
    
    def longest_repeated_substring(self) -> Tuple[str, int]:
        """找出最长重复子串"""
        max_lcp = max(self._lcp)
        if max_lcp == 0:
            return ("", 0)
        
        idx = self._lcp.index(max_lcp)
        pos = self._sa[idx]
        
        return (self._text[pos:pos + max_lcp], max_lcp)
    
    def __repr__(self) -> str:
        return f"SuffixArray('{self._text}')"


def demonstrate_suffix_array():
    """演示后缀数组"""
    text = "banana"
    sa = SuffixArray(text)
    
    print(f"文本: {text}")
    print(f"\n后缀数组: {sa.sa}")
    print(f"排名数组: {sa.rank}")
    print(f"LCP数组: {sa.lcp}")
    
    print(f"\n所有后缀（按字典序）:")
    for i, pos in enumerate(sa.sa):
        suffix = text[pos:]
        lcp = sa.lcp[i] if i > 0 else 0
        print(f"  SA[{i}] = {pos}: '{suffix}' (LCP={lcp})")
    
    pattern = "ana"
    count = sa.count_occurrences(pattern)
    positions = sa.find_all_occurrences(pattern)
    print(f"\n模式 '{pattern}' 出现 {count} 次: {positions}")
    
    lrs, length = sa.longest_repeated_substring()
    print(f"\n最长重复子串: '{lrs}' (长度={length})")


if __name__ == '__main__':
    demonstrate_suffix_array()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

6.4 Unicode编码理论

6.4.1 Unicode的数学模型

定义 6.17（Unicode码点） Unicode码点是 ${0, 1, \ldots, 1114111}$ 中的整数，表示为 $U+XXXX$。

定义 6.18（UTF-8编码） UTF-8是变长编码，将码点编码为1-4字节：

码点范围	UTF-8编码
$U+0000..U+007F$	$0xxxxxxx$
$U+0080..U+07FF$	$110xxxxx\ 10xxxxxx$
$U+0800..U+FFFF$	$1110xxxx\ 10xxxxxx\ 10xxxxxx$
$U+10000..U+10FFFF$	$11110xxx\ 10xxxxxx\ 10xxxxxx\ 10xxxxxx$

定理 6.10（UTF-8自同步性） UTF-8编码具有自同步性：从任意字节开始，最多向前/向后查找1-3字节即可确定字符边界。

证明：UTF-8的设计保证：

首字节以 $0$ 或 $11$ 开头
续字节以 $10$ 开头

因此，检查字节的高2位即可确定其类型。∎

6.4.2 字符串规范化

定义 6.19（Unicode等价性） Unicode定义两种等价性：

规范等价：视觉上不可区分
兼容等价：语义上相同但视觉可能不同

定义 6.20（规范化形式）

形式	描述
NFC	规范分解后规范组合
NFD	规范分解
NFKC	兼容分解后规范组合
NFKD	兼容分解

python

import unicodedata
from typing import List, Tuple

class UnicodeAnalyzer:
    """Unicode分析工具"""
    
    @staticmethod
    def analyze_string(s: str) -> List[dict]:
        """分析字符串中每个字符"""
        result = []
        for char in s:
            result.append({
                'char': char,
                'codepoint': ord(char),
                'name': unicodedata.name(char, 'UNKNOWN'),
                'category': unicodedata.category(char),
                'combining': unicodedata.combining(char),
                'mirrored': unicodedata.mirrored(char),
            })
        return result
    
    @staticmethod
    def normalize_forms(s: str) -> dict:
        """返回所有规范化形式"""
        return {
            'original': s,
            'NFC': unicodedata.normalize('NFC', s),
            'NFD': unicodedata.normalize('NFD', s),
            'NFKC': unicodedata.normalize('NFKC', s),
            'NFKD': unicodedata.normalize('NFKD', s),
        }
    
    @staticmethod
    def utf8_bytes(s: str) -> bytes:
        """获取UTF-8编码字节"""
        return s.encode('utf-8')
    
    @staticmethod
    def analyze_utf8(s: str) -> List[Tuple[int, bytes]]:
        """分析每个字符的UTF-8编码"""
        result = []
        for char in s:
            codepoint = ord(char)
            utf8_bytes = char.encode('utf-8')
            result.append((codepoint, utf8_bytes))
        return result
    
    @staticmethod
    def grapheme_clusters(s: str) -> List[str]:
        """
        分割为字形簇（Grapheme Clusters）
        
        注意：这是简化实现，完整实现需要使用unicode模块
        """
        clusters = []
        current = ""
        
        for char in s:
            if unicodedata.combining(char) > 0:
                current += char
            else:
                if current:
                    clusters.append(current)
                current = char
        
        if current:
            clusters.append(current)
        
        return clusters


def demonstrate_unicode():
    """演示Unicode处理"""
    text = "café"
    
    print(f"原字符串: {text}")
    print(f"长度: {len(text)}")
    
    print("\n规范化形式:")
    forms = UnicodeAnalyzer.normalize_forms(text)
    for name, form in forms.items():
        print(f"  {name}: {form} (len={len(form)})")
    
    print("\nUTF-8编码分析:")
    for codepoint, utf8 in UnicodeAnalyzer.analyze_utf8(text):
        print(f"  U+{codepoint:04X}: {utf8}")
    
    print("\n字符分析:")
    for info in UnicodeAnalyzer.analyze_string(text):
        print(f"  '{info['char']}': U+{info['codepoint']:04X} {info['name']}")


if __name__ == '__main__':
    demonstrate_unicode()

6.5 高级字符串算法

6.5.1 编辑距离

定义 6.21（编辑距离） 字符串 $s$ 和 $t$ 的编辑距离（Levenshtein距离）是将 $s$ 变换为 $t$ 所需的最少单字符操作（插入、删除、替换）次数。

定义 6.22（动态规划） 设 $dp[i][j]$ 为 $s[0..i-1]$ 和 $t[0..j-1]$ 的编辑距离，则：

$$dp[i][j] = \begin{cases} i & \text{if } j = 0 \ j & \text{if } i = 0 \ dp[i-1][j-1] & \text{if } s[i-1] = t[j-1] \ 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) & \text{otherwise} \end{cases}$$

定理 6.11（编辑距离复杂度） 编辑距离可在 $O(mn)$ 时间和 $O(\min(m,n))$ 空间内计算。

python

from typing import List, Tuple

def edit_distance(s: str, t: str) -> int:
    """
    计算编辑距离（Levenshtein距离）
    
    时间复杂度：O(mn)
    空间复杂度：O(min(m, n))
    """
    m, n = len(s), len(t)
    
    if m < n:
        s, t = t, s
        m, n = n, m
    
    prev = list(range(n + 1))
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr[0] = i
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev, curr = curr, prev
    
    return prev[n]


def edit_distance_with_path(s: str, t: str) -> Tuple[int, List[Tuple[str, str]]]:
    """
    计算编辑距离并返回操作序列
    
    返回：(距离, 操作列表)
    操作：('insert', char), ('delete', char), ('replace', old, new), ('match', char)
    """
    m, n = len(s), len(t)
    
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    
    operations = []
    i, j = m, n
    
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s[i - 1] == t[j - 1]:
            operations.append(('match', s[i - 1]))
            i -= 1
            j -= 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            operations.append(('delete', s[i - 1]))
            i -= 1
        elif j > 0 and dp[i][j] == dp[i][j - 1] + 1:
            operations.append(('insert', t[j - 1]))
            j -= 1
        else:
            operations.append(('replace', s[i - 1], t[j - 1]))
            i -= 1
            j -= 1
    
    operations.reverse()
    return dp[m][n], operations


def lcs(s: str, t: str) -> str:
    """
    最长公共子序列
    
    时间复杂度：O(mn)
    空间复杂度：O(mn)
    """
    m, n = len(s), len(t)
    
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    result = []
    i, j = m, n
    
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            result.append(s[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(result))

6.5.2 字符串哈希

定义 6.23（滚动哈希） 滚动哈希允许在 $O(1)$ 时间内计算滑动窗口的哈希值。

定义 6.24（Rabin-Karp哈希） 对于基数 $b$ 和模数 $m$：

$$H(s) = \sum_{i=0}^{n-1} s[i] \cdot b^{n-1-i} \mod m$$

定理 6.12（滚动哈希更新） 若 $H(s[0..n-1])$ 已知，则：

$$H(s[1..n]) = ((H(s[0..n-1]) - s[0] \cdot b^{n-1}) \cdot b + s[n]) \mod m$$

python

from typing import Iterator, List

class RollingHash:
    """
    滚动哈希实现
    
    用于Rabin-Karp字符串匹配
    """
    
    BASE = 256
    MOD = 10**9 + 7
    
    def __init__(self, text: str, window_size: int):
        self._text = text
        self._n = len(text)
        self._window = window_size
        
        self._power = [1] * (window_size + 1)
        for i in range(1, window_size + 1):
            self._power[i] = (self._power[i - 1] * self.BASE) % self.MOD
        
        self._hash = 0
        for i in range(window_size):
            self._hash = (self._hash * self.BASE + ord(text[i])) % self.MOD
    
    def hash(self) -> int:
        """当前窗口的哈希值"""
        return self._hash
    
    def roll(self) -> bool:
        """滑动窗口，返回是否成功"""
        if self._window >= self._n:
            return False
        
        old_char = ord(self._text[self._window - self._n + self._window - 1]) if self._window < self._n else 0
        
        return True
    
    def __iter__(self) -> Iterator[int]:
        """迭代所有窗口的哈希值"""
        yield self._hash
        
        for i in range(self._window, self._n):
            leaving = ord(self._text[i - self._window])
            entering = ord(self._text[i])
            
            self._hash = (self._hash - leaving * self._power[self._window - 1]) % self.MOD
            self._hash = (self._hash * self.BASE + entering) % self.MOD
            
            yield self._hash


def rabin_karp_search(text: str, pattern: str) -> List[int]:
    """
    Rabin-Karp字符串匹配
    
    时间复杂度：平均O(n + m)，最坏O(nm)
    """
    n, m = len(text), len(pattern)
    
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []
    
    BASE = 256
    MOD = 10**9 + 7
    
    power = pow(BASE, m - 1, MOD)
    
    pattern_hash = 0
    for char in pattern:
        pattern_hash = (pattern_hash * BASE + ord(char)) % MOD
    
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * BASE + ord(text[i])) % MOD
    
    result = []
    
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i + m] == pattern:
                result.append(i)
        
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * power) % MOD
            window_hash = (window_hash * BASE + ord(text[i + m])) % MOD
    
    return result

6.6 本章小结

6.6.1 核心定理总结

定理	内容	应用
定理 6.1	字符串连接性质	字符串操作优化
定理 6.5	KMP算法复杂度	模式匹配
定理 6.9	LCP数组线性构造	后缀数组应用
定理 6.10	UTF-8自同步性	编码处理
定理 6.11	编辑距离复杂度	文本比较

6.6.2 模式匹配算法对比

算法	预处理	匹配时间	空间	特点
朴素	-	$O(nm)$	$O(1)$	简单
KMP	$O(m)$	$O(n)$	$O(m)$	确定性
Boyer-Moore	$O(m + \|\Sigma\|)$	$O(n/m)$平均	$O(m + \|\Sigma\|)$	实践快
Rabin-Karp	$O(m)$	$O(n+m)$平均	$O(1)$	多模式
后缀数组	$O(n \log n)$	$O(m \log n)$	$O(n)$	多查询

6.6.3 选择指南

python

# 单次匹配，模式较短
positions = text.find(pattern)  # 内置方法足够

# 多次匹配同一模式
matcher = KMPMatcher(pattern)
for pos in matcher.search(text):
    pass

# 多个模式匹配
patterns = ["a", "b", "c"]
sa = SuffixArray(text)
for p in patterns:
    positions = sa.find_all_occurrences(p)

# 编辑距离
dist = edit_distance(s1, s2)

6.7 习题

理论题

证明：KMP算法的失败函数计算时间为 $O(m)$。
证明：后缀数组的字典序是全序关系。
分析Boyer-Moore算法的最坏情况。
证明：UTF-8编码的自同步性。

设计题

设计一个支持通配符的模式匹配算法。
实现一个基于后缀自动机的字符串匹配器。

实现题

实现一个支持近似匹配（允许k个错误）的字符串搜索。
实现一个Trie树用于字符串集合的高效存储和查询。

6.8 参考文献

Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323-350.
Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762-772.
Karp, R. M., & Rabin, M. O. (1987). Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2), 249-260.
Kasai, T., Lee, G., Arimura, H., Arikawa, S., & Park, K. (2001). Linear-time longest-common-prefix computation in suffix arrays. CPM, 11, 181-192.
Unicode Consortium. (2023). The Unicode Standard, Version 15.0. https://www.unicode.org/versions/Unicode15.0.0/
Crochemore, M., & Rytter, W. (2002). Jewels of Stringology. World Scientific.

下一章：第7章栈与表达式求值理论

第6章 字符串与文本处理理论 ​

本章导读 ​

学习目标 ​

6.1 字符串的形式化理论 ​

6.1.1 字符串的数学定义 ​

6.1.2 字符串ADT规范 ​

6.1.3 字典序与排序 ​

6.2 模式匹配算法理论 ​

6.2.1 问题定义 ​

6.2.2 KMP算法 ​

6.2.3 KMP算法实现 ​

6.2.4 Boyer-Moore算法 ​

6.3 后缀数组理论 ​

6.3.1 后缀数组的定义 ​

6.3.2 LCP数组 ​

6.3.3 后缀数组实现 ​

6.4 Unicode编码理论 ​

6.4.1 Unicode的数学模型 ​

6.4.2 字符串规范化 ​

6.5 高级字符串算法 ​

6.5.1 编辑距离 ​

6.5.2 字符串哈希 ​

6.6 本章小结 ​

6.6.1 核心定理总结 ​

6.6.2 模式匹配算法对比 ​

6.6.3 选择指南 ​

6.7 习题 ​

理论题 ​

设计题 ​

实现题 ​

6.8 参考文献 ​

第6章字符串与文本处理理论

本章导读

学习目标

6.1 字符串的形式化理论

6.1.1 字符串的数学定义

6.1.2 字符串ADT规范

6.1.3 字典序与排序

6.2 模式匹配算法理论

6.2.1 问题定义

6.2.2 KMP算法

6.2.3 KMP算法实现

6.2.4 Boyer-Moore算法

6.3 后缀数组理论

6.3.1 后缀数组的定义

6.3.2 LCP数组

6.3.3 后缀数组实现

6.4 Unicode编码理论

6.4.1 Unicode的数学模型

6.4.2 字符串规范化

6.5 高级字符串算法

6.5.1 编辑距离

6.5.2 字符串哈希

6.6 本章小结

6.6.1 核心定理总结

6.6.2 模式匹配算法对比

6.6.3 选择指南

6.7 习题

理论题

设计题

实现题

6.8 参考文献