pattern_matching/single_pattern/
naive.rs

1// Copyright 2020 Alexander Korn
2//
3// Licensed under the MIT license
4
5/// A simple algorithm for matching a single pattern on a text returning the first occurrence.
6///
7/// Takes a `pattern`, a text `text` and a value `i0` specifying at which index
8/// of the text it should start to search for the next occurence.
9///
10/// If the given text contains the given pattern, the algorithm returns the
11/// index `i` of the first letter of the first occurrence with `i >= i0`.
12/// If the pattern could not be found in the text, `None` is returned.
13///
14/// This algorithm terminates after finding one occurrence of the given pattern
15/// in the given text. If you want to find all occurrences, consider using
16/// [`naive_all`](naive_all) instead.
17///
18/// # Runtime
19///
20/// The worst case runtime is `O(n * m)`, with `n` being the length of the text
21/// (perhaps starting at `i0`) and `m` being the length of the pattern.
22///
23/// # When to Use It
24///
25/// Probably never. This algorithm is the most simple approach to matching a
26/// pattern on a text. Could be useful for comparing runtimes or correctness
27/// with other algorithms.
28///
29/// # How It Works
30///
31/// The algorithm iterates over each index `i` of the text's characters starting
32/// at `i0` and compares the following `m` characters starting at `i` with the
33/// pattern, `m` being the length of the pattern.
34///
35/// After an occurrence has been found, the algorithm returns the index
36/// marking the first character of the occurrence and therefore terminates.
37pub fn naive(pattern: &[u8], text: &[u8], i0: usize) -> Option<usize> {
38    let m = pattern.len();
39    let n = text.len();
40
41    for i in i0..(n - m + 1) {
42        if &text[i..i + m] == pattern {
43            return Some(i);
44        }
45    }
46
47    None
48}
49
50/// A simple algorithm for matching a single pattern on a text returning all occurrences.
51///
52/// Takes a `pattern`, and text `text`.
53///
54/// If the given text contains the given pattern, the algorithm returns the
55/// indexes of the first letters of all found occurrences.
56/// If the pattern could not be found in the text, an empty vector is returned.
57///
58/// # When to Use It
59///
60/// Probably never. This algorithm is the most simple approach to matching a
61/// pattern on a text. Could be useful for comparing runtimes or correctness
62/// with other algorithms.
63///
64/// # How It Works
65///
66/// The algorithm calls the [`naive`](naive) algorithm starting with a the `i0`
67/// parameter being `0`. After the `naive` algorithm returns, it calls that same
68/// algorithm again with an `i0` parameter of the position in text right after
69/// the found occurrence.
70pub fn naive_all(pattern: &[u8], text: &[u8]) -> Vec<usize> {
71    let mut res = Vec::new();
72    let mut i0 = 0;
73
74    while let Some(occ) = naive(pattern, text, i0) {
75        res.push(occ);
76
77        i0 = occ + 1;
78    }
79
80    res
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn test_naive_all() {
89        let text = "gccttaacattattacgccta".as_bytes();
90        let pattern = "tta".as_bytes();
91
92        let mut matches = naive_all(pattern, text);
93        matches.sort_unstable();
94
95        let matches_correct = vec![3, 9, 12];
96
97        assert_eq!(matches, matches_correct);
98    }
99}
pattern_matching/single_pattern/naive.rs

pattern_matching/single_pattern/
naive.rs
