如何找到子字符串在给定字符串(包括关节)中出现的次数?

Question

我的意思是:

let substring = "CNC";

和字符串:

let s = "CNCNC";

在我的版本"联合"就意味着存在2这样的子串。在Rust中，最好的方法是什么?我能想到一些，但基本上是丑陋的C。

我有这样的东西:

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

但是返回1，因为matches()只找到不连接的substrings。

在Rust中最好的方法是什么?

Answer 1

可能有更好的算法。在这里，我只是移动了一个带有子字符串大小的窗口到输入字符串上，并比较该窗口是否与子字符串相同。

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);
}

Answer 2

当你的针/干草堆很小时，遍历所有窗口的方法是完全适用的。事实上，它甚至可能是小针头/干草堆的首选解决方案，因为理论上的最佳解决方案要复杂得多。但随着长度的增加，它会变得相当慢。

虽然Aho-Corasick以支持同时搜索多个模式而闻名，但它可以与单个模式一起使用，以在线性时间内找到重叠的匹配。(在这种情况下，它看起来很像Knuth-Morris-Pratt。)

aho-corasickcrate可以这样做:

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]);
}
}

输出:

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

游乐场:https://play.rust-lang.org/?version=stable&模式= debug&版= 2018,要点= ab6c547b1700bbbc4a29a99adcaceabe