这是一篇翻译向的文章，笔者整理了一些有关Berlekamp–Massey算法的笔记，还增加了一些自己的理解。
下面列出了笔者写此文时所参考的一些资料：
线性递推式
对于一个数列
{
S
i
}
\{S_i\}
{Si}，它的
m
m
m阶递推式
{
Λ
i
}
\{\Lambda_i\}
{Λi}应该始终满足
Λ
1
S
i
+
m
−
1
+
⋯
+
Λ
m
−
1
S
i
+
1
+
Λ
m
S
i
−
S
i
+
m
=
0
\Lambda_1S_{i+m-1}+\cdots+\Lambda_{m-1}S_{i+1}+\Lambda_mS_i-S_{i+m}=0
Λ1Si+m−1+⋯+Λm−1Si+1+ΛmSi−Si+m=0
这里和wikipedia上介绍的略有不同。
BM算法简要介绍
我们记
C
(
x
)
C(x)
C(x)是一个递推式，它的阶数为
L
L
L。BM算法的目的就是对于给定的一个数列
{
S
i
}
\{S_i\}
{Si}，找到一个递推式
C
(
x
)
C(x)
C(x)满足，对于每个指针
k
k
k
C
1
S
k
−
1
+
⋯
+
C
L
−
1
S
k
−
L
+
1
+
C
L
S
k
−
L
−
S
k
=
0
C_1S_{k-1}+\cdots+C_{L-1}S_{k-L+1}+C_LS_{k-L}-S_k=0
C1Sk−1+⋯+CL−1Sk−L+1+CLSk−L−Sk=0
记
d
d
d为上式的值，
B
(
x
)
B(x)
B(x)是上次失配时
C
(
x
)
C(x)
C(x)的副本，
b
b
b为上次失配时
d
d
d的副本，
m
m
m为上次失配后成功迭代的次数
BM算法将通过计算
d
d
d，以逐一检验当前递推式的正确性：
若
d
=
0
d=0
d=0，则成功迭代，检验下一项。
若
d
̸
=
0
d\not=0
d̸=0，则失配，调整新的递推式为
C
′
(
x
)
=
C
(
x
)
−
d
b
x
m
B
(
x
)
C'(x)=C(x)-\frac d bx^mB(x)
C′(x)=C(x)−bdxmB(x)，则这一位的
d
′
=
d
−
d
b
b
=
0
d'=d-\frac d b b=0
d′=d−bdb=0，匹配成功。
请注意，在最优递推式阶数小于等于给定数列长度的一半时，BM算法才能保证求出的递推式最短，否则只能保证求出可行解。
原理
BM算法更像是一个贪心算法，它的正确性在于，我们每次调整当前递推式时，可以保证新的递推式对于以前的项依然满足
d
=
0
d=0
d=0，我们无须再重新开始验证这个新递推式。
把式子展开，则正确性即可证明。
Code
很抱歉，代码咕咕咕了