\(\text{Berlekamp-Massey}\) 算法
考虑维护这个序列 \(a\) 前缀的递推序列 \(f\)。
不妨假设当前考虑到 \(a_1,a_2,a_3\dots a_n\)，当前的递推序列为 \(f_1,f_2,f_3\dots f_m\)，那么接下来分为两种情况：
- \(a_n= \sum _{i=1}^m f_i a_{n-i}\)，那么 \(a_n\) 是符合这一个递推序列的。
- \(a_n \neq \sum_{i=1}^m f_i a_{n-i}\)，考虑记下当前的差值 \(s=a_n-\sum_{i=1}^m f_ia_{n-i}\)，我们称次为发生一个冲突。
找到上一个冲突的位置 \(p\)，不妨记当时的差值为 \(t\)，有 \(a_p - \sum_{i=1}^{m'} f'_i a_{p-i}=t\)。
考虑如果我们能够找到一个递推序列 \(g\) 使得计算出来 \(a_n\) 的值位为 \(1\)，其余为 \(0\)，那么我们就可以令 \(f \leftarrow f+sg\)。
考虑这一个冲突的位置 \(p\) 有什么用，我们可以构造一个递推序列 \(F=\{0,0,0,\dots,0,\dfrac{s}{t},-\dfrac{s}{t} \times f' \}\)，且 \(|F|=n-m+|f'|\)，不难发现我们可以让 \(F\) 成为 \(g\)，显然 \(a_n=1,a_{n-1}=a_{m-1}\dots\)。
关于最短的话感性理解一下好了。