Rust：字符串处理算法
一、字符串处理
字符串处理算法在计算机科学中扮演着重要的角色。它们被广泛应用于文本编辑器、搜索引擎、数据库、生物信息学和密码学等领域。本文将详细介绍字符串处理算法的各个方面，包括字符串匹配、排序、查找、正则表达式匹配和压缩等。
二、字符串匹配算法
字符串匹配算法用于在一个较长的文本串中查找一个模式串。这是一个非常常见的问题，例如在文本编辑器中查找特定单词或短语时就会用到字符串匹配算法。
1. 暴力匹配算法
暴力匹配算法是最简单的字符串匹配算法。它的基本思想是将模式串与文本串中的所有子串进行逐一比较，直到找到匹配的子串或比较完所有子串为止。
下面是一个使用 Rust 语言实现的暴力匹配算法的例子：
fn brute_force_search(text: &str, pattern: &str) -> Option<usize> {
let text_len = text.len();
let pattern_len = pattern.len();
if pattern_len > text_len {
return None;
}
for i in 0..=text_len - pattern_len {
if &text[i..i + pattern_len] == pattern {
return Some(i);
}
}
None
}
这段代码中，brute_force_search 函数接受两个 &str 类型的参数：text 和 pattern，分别表示文本串和模式串。首先，它计算出文本串和模式串的长度，并检查模式串是否比文本串长。如果模式串比文本串长，则返回 None。然后，它遍历文本串中所有可能的子串，并将其与模式串进行比较。如果找到了匹配的子串，则返回其在文本串中的位置。如果遍历完所有子串都没有找到匹配，则返回 None。
暴力匹配算法虽然简单，但其时间复杂度为 O(nm)，其中 n 和 m 分别表示文本串和模式串的长度。当 n 和 m 都很大时，暴力匹配算法的效率会非常低下。
2. KMP 算法
KMP 算法是一种高效的字符串匹配算法，它由 Knuth、Morris 和 Pratt 三人于 1977 年发明。KMP 算法的基本思想是利用已经进行过的比较信息，避免在文本串中进行不必要的回溯。
下面是一个使用 Rust 语言实现的 KMP 算法的例子：
fn kmp_search(text: &str, pattern: &str) -> Option<usize> {
let text_len = text.len();
let pattern_len = pattern.len();
if pattern_len > text_len {
return None;
}
let next = compute_next(pattern);
let mut i = 0;
let mut j = 0;
while i < text_len && j < pattern_len {
if j == usize::MAX || text.as_bytes()[i] == pattern.as_bytes()[j] {
i += 1;
j += 1;
} else {
j = next[j];
}
}
if j == pattern_len {
Some(i - j)
} else {
None
}
}
fn compute_next(pattern next }
这段代码中，kmp_search 函数接受两个 &str 类型的参数：text 和 pattern，分别表示文本串和模式串。首先，它计算出文本串和模式串的长度，并检查模式串是否比文本串长。如果模式串比文本串长，则返回 None。然后，它调用 compute_next 函数计算出模式串的 next 数组。接下来，它初始化两个变量 i 和 j 分别表示当前在文本串和模式串中的位置。然后，它遍历文本串和模式串中的字符。如果当前字符匹配，则将 i 和 j 都加 1；否则，将 j 更新为 next 数组中对应的值。最后，如果模式串遍历完毕，则返回其在文本串中的位置；否则返回 None。
compute_next 函数接受一个 &str 类型的参数 pattern，表示模式串。首先，它计算出模式串的长度，并创建一个长度为 m 的向量 next。然后，它初始化变量 j 为 0，并遍历模式串中的每个字符。对于每个字符，它不断回溯直到找到一个匹配的前缀或回溯到开头为止。如果当前字符与前缀的下一个字符匹配，则将 j 加 1；否则不做任何操作。最后，将 j 的值存储在 next 数组中。
KMP 算法虽然比暴力匹配算法复杂一些，但其时间复杂度为 O(n+m)，其中 n 和 m 分别表示文本串和模式串的长度。当 n 和 m 都很大时，KMP 算法的效率仍然很高。
3. Boyer-Moore 算法
Boyer-Moore 算法是一种高效的字符串匹配算法，它由 Boyer 和 Moore 两人于 1977 年发明。Boyer-Moore 算法的基本思想是从右往左比较模式串和文本串中的字符，并利用已经进行过的比较信息进行跳跃。
下面是一个使用 Rust 语言实现的 Boyer-Moore 算法的例子：
use std::collections::HashMap;
fn boyer_moore_search(text: &str, pattern: &str) -> Option<usize> {
let text_len = text.len();
let pattern_len = pattern.len();
if pattern_len > text_len {
return None;
}
let bc = build_bad_character_shift(pattern);
let gs = build_good_suffix_shift(pattern);
let mut i = 0;
while i <= text_len - pattern_len {
let mut j = (pattern_len - 1) as isize;
while j >= 0 && pattern.as_bytes()[j as usize] == text.as_bytes()[(i + j as usize)] {
j -= 1;
}
if j < 0 {
return Some(i);
} else {
let c = text.as_bytes()[(i + j as usize)];
i += (j as isize - *bc.get(&c).unwrap_or(&-1) as isize).max(gs[j as usize]) as usize;
}
}
None
}
fn build_bad_character_shift(pattern: &str) -> HashMap<u8, usize> {
let m = pattern.len();
let mut bc = HashMap::new();
for i in 0..m {
bc.insert(pattern.as_bytes()[i], i);
}
bc
}
fn build_good_suffix_shift(pattern: &str) -> Vec<usize> {
let m = pattern.len();
let mut gs = vec![0; m];
let mut f = vec![0; m];
f[m - 1] = m;
let mut j = (m - 1) as isize;
for i in (0…m - 1).rev() {
if i > j as usize && f[m - 1 - (i - j as usize)] < i - j as usize {
f[i] = f[m - 1 - (i - j as usize)];
} else {
if i < j as usize {
j = i as isize;
}
while j >= 0 && pattern.as_bytes()[j as usize] == pattern.as_bytes()[m - 1 - (i - j as usize)] {
j -= 1;
}
f[i] = (i - j as usize);
}
}
let mut j = 0;
for i in (0…m).rev() {
if f[i] == i + 1 {
while j < m - 1 - i {
if gs[j] == 0 { gs[j] = m - 1 - i; }
j += 1;
}
}
}
for i in 0…m {
gs[m - 1 - f[i]] = m - 1 - i;
}
gs
}
这段代码中，boyer_moore_search 函数接受两个 &str 类型的参数：text 和 pattern，分别表示文本串和模式串。首先，它计算出文本串和模式串的长度，并检查模式串是否比文本串长。如果模式串比文本串长，则返回 None。然后，它调用 build_bad_character_shift 和 build_good_suffix_shift 函数分别计算出坏字符规则和好后缀规则的跳跃距离。接下来，它初始化变量 i 为 0，并遍历文本串中所有可能的子串。对于每个子串，它从右往左遍历模式串中的字符，并将其与文本串中的字符进行比较。如果找到了不匹配的字符，则根据坏字符规则和好后缀规则计算出跳跃距离，并更新变量 i 的值；否则返回当前子串在文本串中的位置。最后，如果遍历完所有子串都没有找到匹配，则返回 None。
build_bad_character_shift 函数接受一个 &str 类型的参数 pattern，表示模式串。它创建一个哈希映射 bc，并遍历模式串中的每个字符。对于每个字符，它将其及其在模式串中的位置插入哈希映射中。
build_good_suffix_shift 函数接受一个 &str 类型的参数 pattern，表示模式串。它创建两个向量 gs 和 f，并初始化变量 j 为模式串的长度减一。然后，它从右往左遍历模式串中的每个字符。对于每个字符，它根据前面已经进行过的比较信息更新向量 f 中对应元素的值。最后，它根据向量 f 中的值计算出向量 gs 中每个元素的值。
Boyer-Moore 算法虽然比 KMP 算法复杂一些，但其平均时间复杂度为 O(n/m)，其中 n 和 m 分别表示文本串和模式串的长度。当 n 和 m 都很大时，Boyer-Moore 算法的效率仍然很高。
4. Rabin-Karp 算法
Rabin-Karp 算法是一种基于哈希的字符串匹配算法，它由 Rabin 和 Karp 两人于 1987 年发明。Rabin-Karp 算法的基本思想是使用哈希函数对模式串和文本串中的子串进行编码，并将编码后的值进行比
较。
下面是一个使用 Rust 语言实现的 Rabin-Karp 算法的例子：
const BASE: u64 = 101;
fn rabin_karp_search(text: &str, pattern: &str) -> Option<usize> {
let text_len = text.len();
let pattern_len = pattern.len();
if pattern_len > text_len {
return None;
}
let mut h = 1;
for _ in 0..pattern_len - 1 {
h = (h * BASE) % u64::MAX;
}
let mut p = 0;
let mut t = 0;
for i in 0..pattern_len {
p = (BASE * p + pattern.as_bytes()[i] as u64) % u64::MAX;
t = (BASE * t + text.as_bytes()[i] as u64) % u64::MAX;
}
for i in 0..=text_len - pattern_len {
if p == t {
if &text[i..i + pattern_len] == pattern {
return Some(i);
}
}
if i < text_len - pattern_len {
t = (BASE * (t + u64::MAX - h * text.as_bytes()[i] as u64 % u64::MAX) + text.as_bytes()[i + pattern_len] as u64) % u64::MAX;
}
}
None
}
这段代码中，rabin_karp_search 函数接受两个 &str 类型的参数：text 和 pattern，分别表示文本串和模式串。首先，它计算出文本串和模式串的长度，并检查模式串是否比文本串长。如果模式串比文本串长，则返回 None。然后，它初始化变量 h、p 和 t，并计算出模式串和文本串中第一个子串的哈希值。接下来，它遍历文本串中所有可能的子串。对于每个子串，它首先检查其哈希值是否与模式串的哈希值相等。如果相等，则将其与模式串进行比较；否则不做任何操作。最后，如果遍历完所有子串都没有找到匹配，则返回 None。
Rabin-Karp 算法虽然比 Boyer-Moore 算法简单一些，但其平均时间复杂度为 O(n+m)，其中 n 和 m 分别表示文本串和模式串的长度。当 n 和 m 都很大时，Rabin-Karp 算法的效率仍然很高。
三、字符串排序算法
字符串排序算法用于对一组字符串进行排序。这是一个非常常见的问题，例如在数据库中对文本字段进行排序时就会用到字符串排序算法。
- 基数排序
基数排序是一种线性时间复杂度的排序算法，它适用于数据位数固定且范围不大的整数序列。基数排序的基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。
下面是一个使用 Rust 语言实现的基数排序算法的例子：
fn radix_sort(arr: &mut [u32]) {
const BITS: u32 = 8;
const BUCKETS: usize = 1 << BITS;
const MASK: u32 = (1 << BITS) - 1;
let n = arr.len();
let mut b: Vec<Vec<u32>> = Vec::new();
for _ in 0..BUCKETS {
b.push(Vec::with_capacity(n / BUCKETS));
}
for i in 0..(32 / BITS) {
for &x in arr {
let j = ((x >> (i * BITS)) & MASK) as usize;
b[j].push(x);
}
let mut k = 0;
for bucket in &mut b {
for &x in bucket {
arr[k] = x;
k += 1;
}
bucket.clear();
}
}
}
这段代码中，radix_sort 函数接受一个可变的 u32 类型的数组切片作为参数。首先，它定义了一些常量，包括每个位数的比特数 BITS、桶的数量 BUCKETS 和掩码 MASK。然后，它创建一个向量 b，其中包含 BUCKETS 个空向量。接下来，它遍历整数的每个位数，并将每个元素放入正确的桶中。最后，它将各个桶中的元素依次放回原数组中，并清空桶。当循环结束时，数组已经排好序了。
基数排序虽然简单，但其时间复杂度为 O(nk)，其中 n 和 k 分别表示数组长度和最大整数的位数。当 n 和 k 都很大时，基数排序的效率会非常低下。
- 后缀数组
后缀数组是一种用于处理字符串问题的数据结构。它将一个字符串的所有后缀按字典序排序，并存储在一个数组中。后缀数组可以用于解决许多字符串问题，如最长公共前缀、最长重复子串等。
下面是一个使用 Rust 语言实现的后缀数组构建算法的例子：
fn build_suffix_array(s: &str) -> Vec<usize> {
let n = s.len();
let s = s.as_bytes();
let mut sa: Vec<usize> = (0..n).collect();
let mut rank: Vec<usize> = s.iter().map(|&c| c as usize).collect();
let mut temp = vec![0; n];
for k in (0..).map(|i| 1 << i) {
let cmp = |&i: &usize, &j: &usize| -> std::cmp::Ordering {
if rank[i] != rank[j] {
rank[i].cmp(&rank[j])
} else {
let ri = if i + k < n { rank[i + k] } else { n };
let rj = if j + k < n { rank[j + k] } else { n };
ri.cmp(&rj)
}
};
sa.sort_by(cmp);
temp[sa[0]] = 0;
for i in 1…n {
temp[sa[i]] = temp[sa[i - 1]] + if cmp(&sa[i - 1],
&sa[i]) == std::cmp::Ordering::Less { 1 }
else {
0
};
} temp.swap_with_slice(&mut rank);
if rank[sa[n - 1]] == n - 1 { break; }
}
sa
}
这段代码中，build_suffix_array 函数接受一个 &str 类型的参数 s，表示要构建后缀数组的字符串。首先，它计算出字符串的长度 n，并将其转换为字节数组。然后，它创建一个向量 sa，其中包含从 0 到 n-1 的所有整数。接下来，它创建一个向量 rank，其中包含字符串中每个字符的 ASCII 码。最后，它创建一个临时向量 temp，并遍历字符串的每个位数。对于每个位数 k，它定义一个比较函数 cmp，用于比较两个后缀的大小。然后，它根据比较函数对后缀数组进行排序。接着，它更新后缀数组中每个元素的排名，并将其存储在临时向量 temp 中。最后，它将临时向量 temp 中的内容复制回向量 rank 中。当循环结束时，后缀数组已经构建完成。
四、字符串查找算法
四、字符串查找算法
字符串查找算法用于在一个字符串集合中查找特定的字符串。这是一个非常常见的问题，例如在搜索引擎中查找包含特定关键词的网页时就会用到字符串查找算法。
1. Trie 树
Trie 树，又称为字典树，是一种用于快速查找字符串的数据结构。它的基本思想是将字符串集合中的每个字符串拆分成单个字符，并将它们按照公共前缀组织成一棵树。
下面是一个使用 Rust 语言实现的 Trie 树的例子：
use std::collections::HashMap;
#[derive(Default)]
struct Trie {
children: HashMap<char, Trie>,
is_end: bool,
}
impl Trie {
fn new() -> Self {
Default::default()
}
fn insert(&mut self, word: &str) {
let mut node = self;
for c in word.chars() {
node = node.children.entry(c).or_default();
}
node.is_end = true;
}
fn search(&self, word: &str) -> bool {
let mut node = self;
for c in word.chars() {
if let Some(child) = node.children.get(&c) {
node = child;
} else {
return false;
}
}
node.is_end
}
fn starts_with(&self, prefix: &str) -> bool {
let mut node = self;
for c in prefix.chars() {
if let Some(child) = node.children.get(&c) {
node = child;
} else {
return false;
}
}
true
}
}
这段代码中，定义了一个 Trie 结构体，它包含两个字段：children 和 is_end。children 是一个哈希映射，它将字符映射到子节点；is_end 是一个布尔值，表示当前节点是否为一个单词的结尾。
Trie 结构体提供了三个方法：new、insert 和 search。new 方法用于创建一个新 的 Trie 实例；insert 方法用于向 Trie 树中插入一个单词；search 方法用于在 Trie 树中查找一个单词。
2. AC 自动机
AC 自动机，又称为 Aho-Corasick 自动机，是一种用于快速查找多个模式串的数据结构。它基于 Trie 树和有限状态自动机的思想，能够在文本串中同时查找多个模式串。
下面是一个使用 Rust 语言实现的 AC 自动机的例子：
use std::collections::{HashMap, VecDeque};
#[derive(Default)]
struct AcNode {
children: HashMap<char, AcNode>,
fail: Option<Box<AcNode>>,
is_end: bool,
}
impl AcNode {
fn new() -> Self {
Default::default()
}
fn insert(&mut self, word: &str) {
let mut node = self;
for c in word.chars() {
node = node.children.entry(c).or_default();
}
node.is_end = true;
}
fn build(&mut self) {
let mut queue = VecDeque::new();
queue.push_back(self);
while let Some(node) = queue.pop_front() {
for (&c, child) in &node.children {
if let Some(fail) = node.fail.as_ref() {
child.fail = fail.get_child(c);
} else {
child.fail = Some(Box::new(AcNode::new()));
}
queue.push_back(child);
}
}
}
fn get_child(&self, c: char) -> Option<Box<AcNode>> {
if let Some(child) = self.children.get(&c) {
Some(Box::new(child.clone()))
} else if let Some(fail) = self.fail.as_ref() {
fail.get_child(c)
} else {
None
}
}
fn search(&self, text: &str) -> Vec<usize> {
let mut node = self;
let mut result = Vec::new();
for (i, c) in text.char_indices() {
node = node.get_child(c).unwrap_or(self);
let mut temp = node;
while let Some(ref temp_node) = temp {
if temp_node.is_end {
result.push(i);
}
temp = temp_node.fail.as_deref();
}
}
result
}
}
这段代码中，定义了一个 AcNode 结构体，它包含三个字段：children、fail 和 is_end。children 是一个哈希映射，它将字符映射到子节点；fail 是一个可选的 Box<AcNode> 类型，表示当前节点的失配指针；is_end 是一个布尔值，表示当前节点是否为一个单词的结尾。
AcNode 结构体提供了五个方法：new、insert、build、get_child 和 search。new 方法用于创建一个新的 AcNode 实例；insert 方法用于向 AC 自动机中插入一个单词；build 方法用于构建 AC 自动机的失配指针；get_child 方法用于获取当前节点的指定子节点；search 方法用于在 AC 自动机中查找文本串中的所有模式串。
五、正则表达式匹配
正则表达式是一种用于描述字符串模式的语言。它可以用来匹配特定的字符串，或者从文本中提取特定的信息。
下面是一个使用 Rust 语言实现的正则表达式匹配算法的例子：
use regex::Regex;
fn regex_match(text: &str, pattern: &str) -> bool {
let re = Regex::new(pattern).unwrap();
re.is_match(text)
}
这段代码中，regex_match 函数接受两个 &str 类型的参数：text 和 pattern，分别表示文本串和正则表达式模式串。首先，它使用 Regex::new 方法创建一个 Regex 实例。然后，它调用 is_match 方法检查文本串是否与正则表达式模式串匹配。如果匹配，则返回 true；否则返回 false。
正则表达式匹配算法虽然简单，但其时间复杂度取决于正则表达式模式串的复杂度。当模式串非常复杂时，正则表达式匹配算法的效率会非常低下。
六、字符串压缩算法
字符串压缩算法用于减小字符串所占用的存储空间。它通过对字符串进行编码，将其转换为更紧凑的形式，从而减少存储空间的占用。
1. 霍夫曼编码
霍夫曼编码是一种无损压缩算法，它根据字符出现的频率对字符进行变长编码。霍夫曼编码能够有效地减小字符串所占用的存储空间。
下面是一个使用 Rust 语言实现的霍夫曼编码算法的例子：
use std::collections::{BinaryHeap, HashMap};
#[derive(Eq, PartialEq)]
struct HuffmanNode {
freq: usize,
value: Option<char>,
left: Option<Box<HuffmanNode>>,
right: Option<Box<HuffmanNode>>,
}
impl HuffmanNode {
fn new(freq: usize, value: Option<char>) -> Self {
Self {
freq,
value,
left: None,
right: None,
}
}
fn merge(left: HuffmanNode, right: HuffmanNode) -> Self {
Self {
freq: left.freq + right.freq,
value: None,
left: Some(Box::new(left)),
right: Some(Box::new(right)),
}
}
}
impl Ord for HuffmanNode {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.freq.cmp(&self.freq)
}
}
impl PartialOrd for HuffmanNode {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
fn huffman_encode(s: &str) -> (HashMap<char, String>, String) {
let mut freq_map = HashMap::new();
for c in s.chars() {
*freq_map.entry(c).or_insert(0) += 1;
}
let mut heap = BinaryHeap::new();
for (c, f) in freq_map.iter() {
heap.push(HuffmanNode::new(*f, Some(*c)));
}
while heap.len() > 1 {
let left = heap.pop().unwrap();
let right = heap.pop().unwrap();
heap.push(HuffmanNode::merge(left, right));
}
let root = heap.pop().unwrap();
let mut code_map = HashMap::new();
build_code_map(&root, &mut code_map, String::new());
let mut encoded = String::new();
for c in s.chars() {
encoded.push_str(code_map.get(&c).unwrap());
}
(code_map, encoded)
}
fn build_code_map(node: &HuffmanNode, code_map: &mut HashMap<char, String>, code: String) {
if let Some(c) = node.value {
code_map.insert(c, code);
} else {
if let Some(ref left) = node.left {
build_code_map(left, code_map, format!("{}0", code));
}
if let Some(ref right) = node.right {
build_code_map(right, code_map, format!("{}1", code));
}
}
}
2. LZW 算法
LZW 算法是一种无损压缩算法，它基于字典编码的思想，能够有效地减小字符串所占用的存储空间。
下面是一个使用 Rust 语言实现的 LZW 算法的例子：
use std::collections::HashMap;
fn lzw_encode(s: &str) -> Vec<usize> {
let mut dict = HashMap::new();
for i in 0..=255 {
dict.insert(i.to_string(), i);
}
let mut next_code = 256;
let mut w = String::new();
let mut result = Vec::new();
for c in s.chars() {
let wc = format!("{}{}", w, c);
if dict.contains_key(&wc) {
w = wc;
} else {
result.push(dict[&w]);
dict.insert(wc.clone(), next_code);
next_code += 1;
w = c.to_string();
}
}
if !w.is_empty() {
result.push(dict[&w]);
}
result
}
fn lzw_decode(codes: &[usize]) -> String {
let mut dict = HashMap::new();
for i in 0..=255 {
dict.insert(i, (i as u8 as char).to_string());
}
let mut next_code = 256;
let mut w = dict[&codes[0]].clone();
let mut result = w.clone();
for &k in &codes[1..] {
let entry;
if dict.contains_key(&k) {
entry = dict[&k].clone();
} else if k == next_code {
entry = format!("{}{}", w, w.chars().next().unwrap());
} else {
panic!("Invalid LZW code");
}
result.push_str(&entry);
dict.insert(next_code, format!("{}{}", w, entry.chars().next().unwrap()));
next_code += 1;
w = entry;
}
result
}
这段代码中，定义了两个函数：lzw_encode 和 lzw_decode。lzw_encode 函数用于对字符串进行 LZW 编码；lzw_decode 函数用于对 LZW 编码进行解码。
lzw_encode 函数接受一个 &str 类型的参数 s，表示要编码的字符串。首先，它创建一个哈希映射 dict，并将所有单字符字符串及其对应的 ASCII 码插入其中。然后，它初始化变量 next_code 为 256，表示下一个可用的编码。接下来，它创建一个空字符串 w，并遍历字符串 s 中的每个字符。对于每个字符 c，它将其与字符串 w 连接起来，形成一个新字符串 wc。如果 wc 在哈希映射中存在，则将 w 更新为 wc；否则，将哈希映射中 w 对应的编码添加到结果向量中，并将 wc 及其对应的编码插入哈希映射中。最后，如果字符串 w 不为空，则将其对应的编码添加到结果向量中。from刘金，转载请注明原文链接。感谢！
转载自:https://juejin.cn/post/7233749504617136184