Lib.rs

日常开发的基本算法集合

算法列表

搜索算法

• 二分搜索
• Bloom 过滤器
• 二叉树

线段树

• RSQ（范围和查询）
• RMQMin（范围最小查询）
• RMQMax（范围最大查询）

稀疏表

• SparseTableMin（范围最小查询）
• SparseTableMax（范围最大查询）

字符串算法

• Knuth-Morris-Pratt 字符串搜索算法（或 KMP 算法）
• 字典树或前缀树
• Levenshtein 距离（两个符号序列差异的度量）
• 查找最小的字符串周期
• 查找不同的子串
• 后缀数组
• 最长公共前缀
• 查找公共子串（哈希）
• Aho Corasick 算法。在给定字符串中搜索字典中的子串集。

组合和枚举算法

• 排列生成

图算法

• BFS（广度优先搜索）
• DFS（深度优先搜索）
• Dijkstra
• 连通分量
• 强连通分量
• 拓扑排序（用于 DAG）
• Kruskal 算法

数学算法

• 最大公约数（GCD）
• 快速幂
• 模快速幂
• 检查数字是否为素数（费马测试）

数据压缩

• Huffman 算法

数据结构

• DSU（断集合并）

调度

• Johnson 调度算法

示例

extern crate librualg;
use librualg::*;

fn main(){
    let seq = [1, 2, 3, 3, 4, 5];
    assert_eq!(binary_search::upper_bound(&seq, &3), Some(3));
}