How to compare two array if the two arrays are equal, first array is the sub array of the second or vice versa
What do or don't you consider a "sub-array"?
1 Like
If you mean (unordered) "sets" rather than (ordered) arrays, you might like HashSet::is_subset
.
2 Likes
If you care about "order", then you may use "string" match algorithm(eg. KMP). Here is brute force(O(mn)
) solution:
fn sub_array(s: &[i32], t: &[i32]) {
let (m, n) = (s.len(), t.len());
if m < n {
return sub_array(t, s); // swap(t, s)
} else {
for i in 0..m {
let mut j = 0;
while j < n && s[i+j] == t[j] {
j += 1;
}
if j == n {
if n == m {
println!("{:?} = {:?}", s, t);
} else { // m>n
println!("{:?} ∈ {:?}", t, s);
}
return ();
}
}
}
println!("{:?} not in {:?}", t, s);
}
fn main() {
sub_array(&[1, 2, 3, 4, 5], &[2, 3]);
sub_array(&[2, 3], &[1, 2, 3, 4, 5]);
sub_array(&[1], &[5]);
sub_array(&[2, 3], &[2, 3]);
}
If you do not care about "order", then you may use HashMap to count each element, and check s in t
:
fn sub_array(s: &[i32], t: &[i32]) {
let (m, n) = (s.len(), t.len());
if m < n {
return sub_array(t, s); // swap(t, s)
} else {
use std::collections::{HashMap, hash_map::Entry};
let mut cnt_s = HashMap::new();
for &x in s {
cnt_s.entry(x).and_modify(|v| *v += 1).or_insert(1);
}
for &x in t {
match cnt_s.entry(x) {
Entry::Occupied(mut entry) => {
*entry.get_mut() -= 1;
if *entry.get_mut() == 0 { // drop
cnt_s.remove(&x);
}
}
Entry::Vacant(_) => {
println!("{:?} not in {:?}", t, s);
return ();
}
}
}
// t∈s or t=s
if cnt_s.len() == 0 {
println!("{:?} = {:?}", t, s);
} else {
println!("{:?} ∈ {:?}", t, s);
}
}
}
fn main() {
sub_array(&[1, 2, 2, 3, 4, 5], &[2, 2]);
sub_array(&[2, 2, 2], &[1, 2, 2, 3, 4, 5]);
sub_array(&[3, 4], &[1, 2, 3, 4, 5]);
sub_array(&[1], &[5]);
sub_array(&[2, 3, 3], &[2, 3, 3]);
}
1 Like
Thanks for the detailed reply. Let me check if it serve the purpose.
- A = [1, 2, 3], B = [1, 2, 3, 4, 5], A is a sublist of B
- A = [3, 4, 5], B = [1, 2, 3, 4, 5], A is a sublist of B
- A = [3, 4], B = [1, 2, 3, 4, 5], A is a sublist of B
- A = [1, 2, 3], B = [1, 2, 3], A is equal to B
- A = [1, 2, 3, 4, 5], B = [2, 3, 4], A is a superlist of B
- A = [1, 2, 4], B = [1, 2, 3, 4, 5], A is not a superlist of, sublist of or equal to B
1 Like
Searching for existing crates with a general (i.e. supporting all kinds of item types) efficient sub-string search algorithm, I came across e.g. this one: https://crates.io/crates/galil-seiferas
For string-search on str
or [u8]
in particular, there seems to be a lot more options.
1 Like