How to find the number of times that a substring occurs in a given string (include jointed)?

user_10843767 0
Viewed 99

By jointed I mean:

let substring = "CNC";

And the string:

let s = "CNCNC";

In my version "jointed" would mean that there are 2 such substrings present. What is the best way of doing that in Rust? I can think of a few but then it's basically ugly C.

I have something like that:

fn find_a_string(s: &String, sub_string: &String) -> u32 {
    s.matches(sub_string).count() as u32
}

But that returns 1, because matches() finds only disjointed substrings.

What's the best way to do that in Rust?

rust algorithm string
2 Answers

Probably there is a better algorithm. Here I just move a window with the size of the sub-string we are looking for over the input string and compare if that window is the same as the substring.

fn main() {
    let string = "aaaa";
    let substring = "aa";

    let substrings = string
        .as_bytes()
        .windows(substring.len())
        .filter(|&w| w == substring.as_bytes())
        .count();

    println!("{}", substrings);
}
user_25888000

The approach of iterating over all windows is perfectly serviceable when your needle/haystack is small. And indeed, it might even be the preferred solution for small needles/haystacks, since a theoretically optimal solution is a fair bit more complicated. But it can get quite a bit slower as the lengths grow.

While Aho-Corasick is more well known for its support for searching multiple patterns simultaneously, it can be used with a single pattern to find overlapping matches in linear time. (In this case, it looks a lot like Knuth-Morris-Pratt.)

The aho-corasick crate can do this:

use aho_corasick::AhoCorasick;

fn main() {
    let haystack = "CNCNC";
    let needle = "CNC";
    let matcher = AhoCorasick::new(&[needle]);
    for m in matcher.find_overlapping_iter(haystack) {
        let (s, e) = (m.start(), m.end());
        println!("({:?}, {:?}): {:?}", s, e, &haystack[s..e]);
    }
}

Output:

(0, 3): "CNC"
(2, 5): "CNC"

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ab6c547b1700bbbc4a29a99adcaceabe

user_6192160
Related