alg-seq 0.0.2

Crate containing implementations for algorithms introduced in the AlgSeq lecture at university of Kiel
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

/// Naive pattern matching.
/// Compare every position in the text to every position in the pattern.
pub fn naive(pattern: &String, text: &String) -> Vec<usize> {
    let pattern_chars = pattern.chars();
    let text_chars = text.chars();

    let mut positions: Vec<usize> = Vec::new();

    'outter: for i in 0..text.len() {
        for (j, p) in pattern_chars.clone().enumerate() {
            // check, if we overflow the boundaries of the text
            if i + j >= text.len() {
                return positions;
            }
            // quit, if characters do not match
            if p != text_chars.clone().nth(i + j).unwrap() {
                continue 'outter;
            }
        }
        positions.push(i);
    }
    return positions;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_naive_simple() {
        let pattern = "ana".to_string();
        let text = "banana".to_string();

        let res = naive(&pattern, &text);
        assert_eq!(res, vec![1, 3]);
    }

    #[test]
    fn test_naive_complex() {
        let pattern = "ban".to_string();
        let text = "bananbnanabanbnnban".to_string();

        let res = naive(&pattern, &text);
        assert_eq!(res, vec![0, 10, 16]);
    }
}