Alcs

所有最长公共子串和 Rust 的模糊字符串搜索

访问 crates.io 的链接

实现了 所有子串公共子序列算法

给定两个字符串 s1 和 s2，可以在 O(|s1|*|s2|) 的时间和 O(|s1|+|s2|) 的空间内构造一个结构，可以查询以找到 s1 和 s2 所有可能的子串之间的所有最长公共子序列的长度，每次查询需要常数时间。

提供了一些访问函数来检索论文中定义的矩阵和向量

所有 LCS

extern crate alcs;
use alcs::Alcs;

fn main() {
   let a = "word";
   let b = "hello world";
   let va = a.chars().collect::<Vec<char>>();
   let vb = b.chars().collect::<Vec<char>>();
   let alcs = Alcs::new(&va, &vb);
   for i in 0..b.len() {
       for (i, j, cij) in alcs.suffix(i) {
           println!(r#"LCS between "{}" and "{}" has length {}"#,a,&b[i..j],cij);
       }
    }
}

输出

LCS between "word" and "h" has length 0
LCS between "word" and "he" has length 0
LCS between "word" and "hel" has length 0
...
LCS between "word" and " world" has length 4
LCS between "word" and "w" has length 1
LCS between "word" and "wo" has length 2
LCS between "word" and "wor" has length 3
...
LCS between "word" and "d" has length 1

模糊子串

此外，还定义了一个 trait，允许进行字符串模糊搜索

extern crate alcs;
use alcs::FuzzyStrstr;

fn main() {
   let tsh = 0.7;
   let tests = [
       ("he.llo.wor.ld.!", "world"),
       ("he.llo.word", "world"),
       ("hello world", "word"),
       ("hello world", "banana"),
   ];
   for &(h, n) in &tests {
       match h.fuzzy_find_str(n, tsh) {
           None => {
               println!(r#""{}" does not contain "{}""#, h, n);
           }
           Some((score, sub)) => {
               println!(r#""{}" contains "{}" ("{}") with score {}"#, h, n, sub, score);
           }
       }
   }
}

输出

 "he.llo.wor.ld.!" contains "world" ("wor.ld") with score 0.8333333
 "he.llo.word" contains "world" ("word") with score 0.8
 "hello world" contains "word" ("world") with score 0.8
 "hello world" does not contain "banana"