competitive/string/
wildcard_pattern_matching.rs

1use super::{Convolve, ConvolveSteps, Zero, montgomery};
2
3pub fn wildcard_pattern_matching(p: &[u8], s: &[u8]) -> Vec<bool> {
4    type M = montgomery::MInt2013265921;
5    let n = p.len();
6    let m = s.len();
7    assert!(n >= 1);
8    assert!(m >= 1);
9    let mut sum = vec![M::zero(); m - n + 1];
10    macro_rules! add {
11        ($f:expr; $g:expr;) => {{
12            let x: Vec<M> = p.iter().map($f).rev().collect();
13            let y: Vec<M> = s.iter().map($g).collect();
14            let z = Convolve::<montgomery::Modulo2013265921>::convolve(x, y);
15            for i in 0..=m - n {
16                sum[i] += z[n + i - 1];
17            }
18        }};
19    }
20    add!(
21        |&x: &u8| M::from((x != b'?') as u32 * x as u32 * x as u32);
22        |&x: &u8| M::from((x != b'?') as u32);
23    );
24    add!(
25        |&x: &u8| -M::from((x != b'?') as u32 * x as u32 * 2);
26        |&x: &u8| M::from((x != b'?') as u32 * x as u32);
27    );
28    add!(
29        |&x: &u8| M::from((x != b'?') as u32);
30        |&x: &u8| M::from((x != b'?') as u32 * x as u32 * x as u32);
31    );
32    sum.into_iter().map(|s| s.is_zero()).collect()
33}