Berlekamp-Massey

線形漸化式\( a_i = c_0 * a_(i - 1) + c_1 * a_(i - 2) + ... \)があって、数列\(a\)がわかっているときに、漸化式の係数\(c\)を\(O(n^2)\)で求める.

Code

#include <vector>

template<class F>
std::vector<F> berlekamp_massey(const std::vector<F>& s) {
  int n = s.size();
  std::vector<F> b { F(1) };
  std::vector<F> c { F(1) };
  F y(1);
  int shift = 0;
  for(int len = 0; len < n; len++) {
    shift++;
    F x(0);
    for(int i = 0; i < c.size(); i++) {
      x += c[i] * s[len - i];
    }
    if(x == F(0)) { continue; }
    std::vector<F> old_c = c;
    F freq = x / y; c.resize(std::max(c.size(), b.size() + shift), F(0));
    for(int i = 0; i < b.size(); i++) {
      c[i + shift] -= freq * b[i];
    }
    if(old_c.size() < c.size()) {
      b = std::move(old_c);
      y = x;
      shift = 0;
    }
  }
  std::vector<F> ans(c.size() - 1);
  for(int i = 1; i < c.size(); i++) {
    ans[i - 1] = -c[i];
  }
  return ans;
}