competitive/math/
berlekamp_massey.rs

1use super::{One, Zero};
2use std::{
3    mem::swap,
4    ops::{Add, Div, Mul, Sub},
5};
6
7pub fn berlekamp_massey<T>(a: &[T]) -> Vec<T>
8where
9    T: Zero
10        + One
11        + Clone
12        + PartialEq
13        + Add<Output = T>
14        + Sub<Output = T>
15        + Mul<Output = T>
16        + Div<Output = T>,
17{
18    let n = a.len();
19    let mut b = Vec::with_capacity(n + 1);
20    let mut c = Vec::with_capacity(n + 1);
21    let mut tmp = Vec::with_capacity(n + 1);
22    b.push(T::one());
23    c.push(T::one());
24    let mut y = T::one();
25    for k in 1..=n {
26        let clen = c.len();
27        let mut x = T::zero();
28        for (c, a) in c.iter().zip(&a[k - clen..]) {
29            x = x + c.clone() * a.clone();
30        }
31        b.push(T::zero());
32        let blen = b.len();
33        if x.is_zero() {
34            continue;
35        }
36        let freq = x.clone() / y.clone();
37        if clen < blen {
38            swap(&mut c, &mut tmp);
39            c.clear();
40            c.resize_with(blen - clen, T::zero);
41            c.extend(tmp.iter().cloned());
42            for (c, b) in c.iter_mut().rev().zip(b.iter().rev()) {
43                *c = c.clone() - freq.clone() * b.clone();
44            }
45            swap(&mut b, &mut tmp);
46            y = x;
47        } else {
48            for (c, b) in c.iter_mut().rev().zip(b.iter().rev()) {
49                *c = c.clone() - freq.clone() * b.clone();
50            }
51        }
52    }
53    c.reverse();
54    c
55}
competitive/math/berlekamp_massey.rs

competitive/math/
berlekamp_massey.rs
