(
input_string: &[T],
pattern: &[T],
start_index: usize,
only_full_matches: bool,
)
| 1 | fn match_with_z_array<T: Eq>( |
| 2 | input_string: &[T], |
| 3 | pattern: &[T], |
| 4 | start_index: usize, |
| 5 | only_full_matches: bool, |
| 6 | ) -> Vec<usize> { |
| 7 | let size = input_string.len(); |
| 8 | let pattern_size = pattern.len(); |
| 9 | let mut last_match: usize = 0; |
| 10 | let mut match_end: usize = 0; |
| 11 | let mut array = vec![0usize; size]; |
| 12 | for i in start_index..size { |
| 13 | // getting plain z array of a string requires matching from index |
| 14 | // 1 instead of 0 (which gives a trivial result instead) |
| 15 | if i <= match_end { |
| 16 | array[i] = std::cmp::min(array[i - last_match], match_end - i + 1); |
| 17 | } |
| 18 | while (i + array[i]) < size && array[i] < pattern_size { |
| 19 | if input_string[i + array[i]] != pattern[array[i]] { |
| 20 | break; |
| 21 | } |
| 22 | array[i] += 1; |
| 23 | } |
| 24 | if (i + array[i]) > (match_end + 1) { |
| 25 | match_end = i + array[i] - 1; |
| 26 | last_match = i; |
| 27 | } |
| 28 | } |
| 29 | if !only_full_matches { |
| 30 | array |
| 31 | } else { |
| 32 | let mut answer: Vec<usize> = vec![]; |
| 33 | for (idx, number) in array.iter().enumerate() { |
| 34 | if *number == pattern_size { |
| 35 | answer.push(idx); |
| 36 | } |
| 37 | } |
| 38 | answer |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | #[allow(dead_code)] |
| 43 | pub fn z_array<T: Eq>(input: &[T]) -> Vec<usize> { |
no test coverage detected