Enum ConvolveRealFft 

pub enum ConvolveRealFft {}

Implementations

impl ConvolveRealFft

pub fn middle_product_f64( a: impl ExactSizeIterator<Item = f64>, b: impl ExactSizeIterator<Item = f64>, ) -> Vec<f64>

Returns coefficients b.len() - 1..a.len() of the convolution of a and b. Panics unless 0 < b.len() <= a.len().

Examples found in repository

crates/competitive/src/string/wildcard_pattern_matching.rs (lines 19-22)

fn wildcard_pattern_matching_with_rng(p: &[u8], s: &[u8], rng: &mut Xorshift) -> Vec<bool> {
    assert!(!p.is_empty());
    assert!(p.len() <= s.len());
    let mut direct = [0.0; 256];
    let mut inverse = [0.0; 256];
    for i in 0..256 {
        let x = 1.25 + 0.75 * rng.randf();
        direct[i] = x;
        inverse[i] = 1.0 / x;
    }
    direct[b'?' as usize] = 0.0;
    inverse[b'?' as usize] = 0.0;
    ConvolveRealFft::middle_product_f64(
        s.iter().map(|&c| direct[c as usize]),
        p.iter().rev().map(|&c| inverse[c as usize]),
    )
    .into_iter()
    .map(|x| (x - x.round()).abs() < 1e-8)
    .collect()
}

Trait Implementations

impl ConvolveSteps for ConvolveRealFft

type T = Vec<i64>

type F = Vec<Complex<f64>>

fn length(t: &Self::T) -> usize

fn transform(t: Self::T, len: usize) -> Self::F

fn inverse_transform(f: Self::F, len: usize) -> Self::T

fn convolve(a: Self::T, b: Self::T) -> Self::T

fn multiply(f: &mut Self::F, g: &Self::F)

const CYCLIC: bool = false

Whether transform multiplication computes modulo x^n - 1 in the coefficient ring.

fn square(t: Self::T, len: usize) -> Self::T

where Self::T: Clone,