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

#![warn(missing_docs)]

//! # Similar String - the library for finding string similarities
//! 
//! With this library you can easily find rate of similarity of two strings or array of strings.
//! Under the hood LCS (length finding variant) algorithm is used with O(n * m) time complexity and O(1) memory complexity.
//! 
//! # Example
//! ```
//! use similar_string::{compare_similarity, find_best_similarity};
//! 
//! compare_similarity("age", "page"); // 0.75
//! find_best_similarity("fight", &vec!["blight", "night", "stride"]); // ("night", 0.8)
//! ```
//! 
//! # LCS Algorithm
//! 
//! You can also use the `lcs_length` that is used under the hood to compute length of longest common subsequence.
//! 
//! ```
//! use similar_string::lcs_length;
//! 
//! // The longest common subsequence in this case is "one"
//! lcs_length("longest", "stone"); // 3
//! ```

use std::cmp::max;

#[inline]
fn get_shorter_longer_strings(left: impl AsRef<str>, right: impl AsRef<str>) -> (String, String) {
    (left.as_ref().to_string(), right.as_ref().to_string())
}

/// Get length of the longest common subsequence
pub fn lcs_length(left: impl AsRef<str>, right: impl AsRef<str>) -> usize {
    let (left, right) = get_shorter_longer_strings(left, right);
    let mut table = vec![vec![0 as usize; left.len() + 1]; 2];

    for rletter in right.chars() {
        for (col, lletter) in left.chars().enumerate() {
            if rletter == lletter {
                table[1][col + 1] = 1 + table[0][col];
            } else {
                table[1][col + 1] = max(table[0][col + 1], table[1][col]);
            }
        }
        table[0] = table.pop().unwrap();
        table.push(vec![0 as usize; left.len() + 1]);
    }
    *table[0].last().unwrap()
}

/// Get score of similarity of two certain strings
pub fn compare_similarity(left: impl AsRef<str>, right: impl AsRef<str>) -> f64 {
    let (len1, len2) = (left.as_ref().len(), right.as_ref().len());
    let lcs_len = lcs_length(left.as_ref(), right.as_ref());
    let size = max(len1, len2);
    lcs_len as f64 / size as f64
}

/// Find the string amongs the options that is the most similar to the target one
pub fn find_best_similarity(taregt: impl AsRef<str>, options: &[impl AsRef<str>]) -> (String, f64) {
    let mut high_score: f64 = -1.0;
    let mut position: usize = 0;
    for (index, option) in options.iter().enumerate() {
        let score = compare_similarity(option.as_ref(), taregt.as_ref());
        if score > high_score {
            high_score = score;
            position = index;
        }
    }
    (options[position].as_ref().to_string(), high_score)
}

#[cfg(test)]
mod tests {
    use std::collections::HashSet;

    use crate::*;

    #[test]
    fn lcs_works() {
        let length = lcs_length("longest", "stone");
        assert_eq!(length, 3);
    }

    #[test]
    fn identity_check() {
        let score = compare_similarity("hello", "hello");
        assert_eq!(score, 1.0);
    }

    #[test]
    fn ratio_is_symetrical() {
        let left = "longest";
        let right = "stone";
        let score1 = compare_similarity(left, right);
        let score2 = compare_similarity(right, left);
        assert_eq!(score1, score2);
    }

    #[test]
    fn find_best() {
        let target = "fight";
        let options = vec!["blight", "night", "stride"];
        let (matched, score) = find_best_similarity(target, &options);
        assert_eq!(matched, "night");
        assert_eq!(score, 0.8);
    }

    #[test]
    fn find_best_with_set() {
        let target = format!("fight");
        let mut options = HashSet::new();
        options.insert("blight");
        options.insert("night");
        options.insert("stride");
        let vector: Vec<_> = options.iter().collect();
        let (matched, score) = find_best_similarity(target, &vector);
        assert_eq!(matched, "night");
        assert_eq!(score, 0.8);
    }
}