Array Comparison

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