competitive/string/
wildcard_pattern_matching.rs

1use super::{ConvolveRealFft, Xorshift};
2
3pub fn wildcard_pattern_matching(p: &[u8], s: &[u8]) -> Vec<bool> {
4    wildcard_pattern_matching_with_rng(p, s, &mut Xorshift::new())
5}
6
7fn wildcard_pattern_matching_with_rng(p: &[u8], s: &[u8], rng: &mut Xorshift) -> Vec<bool> {
8    assert!(!p.is_empty());
9    assert!(p.len() <= s.len());
10    let mut direct = [0.0; 256];
11    let mut inverse = [0.0; 256];
12    for i in 0..256 {
13        let x = 1.25 + 0.75 * rng.randf();
14        direct[i] = x;
15        inverse[i] = 1.0 / x;
16    }
17    direct[b'?' as usize] = 0.0;
18    inverse[b'?' as usize] = 0.0;
19    ConvolveRealFft::middle_product_f64(
20        s.iter().map(|&c| direct[c as usize]),
21        p.iter().rev().map(|&c| inverse[c as usize]),
22    )
23    .into_iter()
24    .map(|x| (x - x.round()).abs() < 1e-8)
25    .collect()
26}
27
28#[cfg(test)]
29mod tests {
30    use super::{wildcard_pattern_matching, wildcard_pattern_matching_with_rng};
31    use crate::tools::Xorshift;
32    use crate::tools::testutil::{exhaustive_sequences, sample_usize};
33
34    #[test]
35    fn test_wildcard_pattern_matching() {
36        let mut rng = Xorshift::default();
37        let inputs: Vec<_> = exhaustive_sequences([0, b'?', u8::MAX], 0..=5)
38            .filter(|s| !s.is_empty())
39            .collect();
40        let mut cases: Vec<_> = inputs
41            .iter()
42            .flat_map(|p| {
43                inputs
44                    .iter()
45                    .filter(|s| s.len() >= p.len())
46                    .map(move |s| (p.clone(), s.clone()))
47            })
48            .collect();
49        for _ in 0..1000 {
50            let n = rng.rand(128) as usize + 1;
51            let m = n + rng.rand(256) as usize;
52            let mut p: Vec<_> = (0..n).map(|_| b"abc?"[rng.rand(4) as usize]).collect();
53            let mut s: Vec<_> = (0..m).map(|_| b"abc?"[rng.rand(4) as usize]).collect();
54            match rng.rand(4) {
55                0 => p.copy_from_slice(&s[..n]),
56                1 => p.fill(b'?'),
57                2 => s.fill(b'?'),
58                _ => {}
59            }
60            cases.push((p, s));
61        }
62        for n in sample_usize(&mut rng, 16, 0..=1024, 0)
63            .into_iter()
64            .filter(|&n| n != 0)
65        {
66            for c in 0..=u8::MAX {
67                let p = vec![c; n];
68                assert_eq!(wildcard_pattern_matching(&p, &p), [true]);
69                assert_eq!(wildcard_pattern_matching(&vec![b'?'; n], &p), [true]);
70            }
71        }
72        for (p, s) in cases {
73            let expected: Vec<_> = (0..=s.len() - p.len())
74                .map(|i| {
75                    p.iter()
76                        .zip(&s[i..])
77                        .all(|(&a, &b)| a == b || a == b'?' || b == b'?')
78                })
79                .collect();
80            assert_eq!(
81                expected,
82                wildcard_pattern_matching_with_rng(&p, &s, &mut Xorshift::default()),
83                "pattern={p:?}, text={s:?}"
84            );
85        }
86    }
87}
competitive/string/wildcard_pattern_matching.rs

competitive/string/
wildcard_pattern_matching.rs
