Блог

Главная - Вопросы по программированию - Как определить, сколько раз подстрока встречается в данной строке (включая соединенную)?

Как определить, сколько раз подстрока встречается в данной строке (включая соединенную)?

#string #algorithm #rust

Вопрос:

Под сочленением я имею в виду:

 let substring = "CNC";

И струна:

 let s = "CNCNC";

В моей версии «соединено» означало бы, что 2 такие подстроки присутствуют.
Каков наилучший способ сделать это Rust ? Я могу придумать несколько, но тогда это в основном уродливо C .

У меня есть что-то вроде этого:

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

Но это возвращается 1 , потому matches() что находит только разрозненные substrings .

Как лучше всего это сделать в Rust?

Комментарии:

1. docs.rs/memchr/2.4.1/memchr/memmem/fn.find_iter.html

2. таким образом, я не знаю результата для вашего случая

Ответ №1:

Вероятно, есть лучший алгоритм. Здесь я просто перемещаю окно с размером подстроки, которую мы ищем, поверх входной строки и сравниваю, совпадает ли это окно с подстрокой.

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

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

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

Ответ №2:

Метод перебора всех окон вполне пригоден, когда ваша иголка/стог сена невелики. И действительно, это может быть даже предпочтительным решением для небольших иголок/стогов сена, поскольку теоретически оптимальное решение намного сложнее. Но по мере увеличения длины он может становиться все медленнее.

В то время как Aho-Corasick более известен своей поддержкой одновременного поиска нескольких шаблонов, его можно использовать с одним шаблоном для поиска совпадений в линейном времени. (В данном случае это очень похоже на Кнута-Морриса-Пратта.)

aho-corasick Ящик может это сделать:

 use aho_corasick::AhoCorasick;

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

Выход:

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

Игровая площадка: https://play.rust-lang.org/?version=stableamp;mode=debugamp;edition=2018amp;gist=ab6c547b1700bbbc4a29a99adcaceabe

Метки: ,