这是一篇翻译向的文章，笔者整理了一些有关 Berlekamp–Massey 算法的笔记，还增加了一些自己的理解。

下面列出了笔者写此文时所参考的一些资料：

• wikipedia
• fjzzq2002
• 别人的博客

线性递推式

对于一个数列 ${S_i}$，它的 $m$阶递推式 ${\Lambda_i}$应该始终满足

$$\Lambda_1S_{i+m-1}+\cdots+\Lambda_{m-1}S_{i+1}+\Lambda_mS_i-S_{i+m}=0$$

这里和 wikipedia 上介绍的略有不同。

BM 算法简要介绍

我们记 $C(x)$是一个递推式，它的阶数为 $L$。BM 算法的目的就是对于给定的一个数列 ${S_i}$，找到一个递推式 $C(x)$满足，对于每个指针 $k$

$$C_1S_{k-1}+\cdots+C_{L-1}S_{k-L+1}+C_LS_{k-L}-S_k=0$$

记 $d$为上式的值，$B(x)$是上次失配时 $C(x)$的副本，$b$为上次失配时 $d$的副本，$m$为上次失配后成功迭代的次数

BM 算法将通过计算 $d$，以逐一检验当前递推式的正确性：

若 $d=0$，则成功迭代，检验下一项。
若 $d\not=0$，则失配，调整新的递推式为 $C'(x)=C(x)-\frac d bx^mB(x)$，则这一位的 $d’=d-\frac d b b=0$，匹配成功。

请注意，在最优递推式阶数小于等于给定数列长度的一半时，BM 算法才能保证求出的递推式最短，否则只能保证求出可行解。

原理

BM 算法更像是一个贪心算法，它的正确性在于，我们每次调整当前递推式时，可以保证新的递推式对于以前的项依然满足 $d=0$，我们无须再重新开始验证这个新递推式。

把式子展开，则正确性即可证明。

Code

很抱歉，代码咕咕咕了