librualg 0.29.1

Collection of basic algorithms for everyday development
Documentation 
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

extern crate librualg;

use librualg::*;
use librualg::string::levenshtein_distance;
use std::collections::BTreeMap;

#[test]
fn kmp(){
    assert_eq!(string::kmp("ababcxabdabcxabcxabcde", "abcxabcde"), vec![13]);
    assert_eq!(string::kmp("a", "ab"), vec![]);
    assert_eq!(string::kmp("aaaaa", "a"), vec![0, 1, 2, 3, 4]);
    assert_eq!(string::kmp("abcdabcd", "abc"), vec![0, 4]);
}

#[test]
fn kmp_first(){
    assert_eq!(string::kmp_first("ababcxabdabcxabcxabcde", "abcxabcde"), Some(13));
    assert_eq!(string::kmp_first("a", "ab"), None);
    assert_eq!(string::kmp_first("aaaaa", "a"), Some(0));
    assert_eq!(string::kmp_first("ebcdabcd", "abc"), Some(4));
}

#[test]
fn test_levenshtein_distance(){
    assert_eq!(levenshtein_distance("POLYNOMIAL", "EXPONENTIAL", 1, 1, 1), 6);
    assert_eq!(levenshtein_distance("abcdasdasd", "cddabcd", 1, 1, 1), 6);
    assert_eq!(levenshtein_distance("", "", 1, 1, 1), 0);
    assert_eq!(levenshtein_distance("aaa", "aaa", 1, 1, 1), 0);
    assert_eq!(levenshtein_distance("", "aaa", 1, 1, 1), 3);
}

#[test]
fn test_minimum_string_period() {
    assert_eq!(string::minimum_string_period("abcabcabca"), "abc");
    assert_eq!(string::minimum_string_period("abcdefg"), "abcdefg");
}

#[test]
fn test_distinct_substrings(){
    assert_eq!(string::distinct_substrings("a"), vec!["a"]);
    assert_eq!(string::distinct_substrings("aaaa"), vec!["a", "aa", "aaa", "aaaa"]);
    assert_eq!(string::distinct_substrings(""), Vec::<&str>::new());
    let mut values = string::distinct_substrings("abaaba");
    values.sort();
    assert_eq!(values, vec!["a", "aa", "aab", "aaba", "ab", "aba", "abaa", "abaab", "abaaba", "b", "ba", "baa", "baab", "baaba"]);
}

#[test]
fn test_suffix_array() {
    assert_eq!(string::suffix_array("ababba$").0, vec![6, 5, 0, 2, 4, 1, 3]);
    assert_eq!(string::suffix_array("bababa$").0, vec![6, 5, 3, 1, 4, 2, 0]);
}

#[test]
fn test_lcp() {
    let (p, c) = string::suffix_array("ababba$");
    let data = string::Lcp::build(&p, &c, "ababba$");
    assert_eq!(data.lcp(0, 5), Some(1));
    assert_eq!(data.lcp(0, 1), Some(0));
    assert_eq!(data.lcp(1, 4), Some(2));
    assert_eq!(data.lcp(4, 1), Some(2));

}

#[test]
fn test_hash() {
    assert_eq!(string::hash("abcdabcd"), 2842022591228);
}

#[test]
fn test_common_substring() {
    assert_eq!(string::common_substring("VOTEFORTHEGREATALBANIAFORYOU", "CHOOSETHEGREATALBANIANFUTURE"), Some("THEGREATALBANIA"));
    assert_eq!(string::common_substring("aba", "cabdd"), Some("ab"));
    assert_eq!(string::common_substring("aaaaa", "bbaaa"), Some("aaa"));
    assert_eq!(string::common_substring("", "bbaaa"), None);
    assert_eq!(string::common_substring("abcde", "abcde"), Some("abcde"));
    assert_eq!(string::common_substring("aaaaaaaaaaaaaaaaaaaaaaaaab", "aaaaaaaaaaaaaaaaaaaaaaaaac"), Some("aaaaaaaaaaaaaaaaaaaaaaaaa"));
}

#[test]
fn test_aho_corasick() {
    let mut dict = ["aba", "abb", "bbca"];
    let t = "abaabbbbca";
    let mut res = string::aho_corasick(&dict, t);

    let mut m = BTreeMap::new();
    m.insert(0, vec![0]);
    m.insert(1, vec![3]);
    m.insert(2, vec![6]);
    assert_eq!(m, res);

    let t = "abaabbbbcaaba";
    res = string::aho_corasick(&dict, t);

    m = BTreeMap::new();
    m.insert(0, vec![0, 10]);
    m.insert(1, vec![3]);
    m.insert(2, vec![6]);
    assert_eq!(m, res);

    let t = "abaabbbbcaba";
    res = string::aho_corasick(&dict, t);

    m = BTreeMap::new();
    m.insert(0, vec![0, 9]);
    m.insert(1, vec![3]);
    m.insert(2, vec![6]);
    assert_eq!(m, res);

    dict = ["abba", "bb", "cc"];
    let t = "abba";
    res = string::aho_corasick(&dict, t);

    m = BTreeMap::new();
    m.insert(0, vec![0]);
    m.insert(1, vec![1]);
    assert_eq!(m, res);

    dict = ["aba", "baba", "cc"];
    let t = "ababababa";
    res = string::aho_corasick(&dict, t);

    m = BTreeMap::new();
    m.insert(0, vec![0, 2, 4, 6]);
    m.insert(1, vec![1, 3, 5]);
    assert_eq!(m, res);

}