#include <stdio.h>
#include <memory.h>
#define MAXL (1000)
typedef unsigned char uchar;
void prints(const uchar *s, const int n)
{
int i;
for(i=0;i<n;i++) {printf("%u",s[i]);}
printf("\n");
}
//implement the Berlekamp–Massey algorithm for binary sequences.
//Please see https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm#The_algorithm_for_the_binary_field
int bm(const uchar*s, const int n)
{
int i,j,lc,m,d;
uchar b[MAXL];
uchar c[MAXL];
uchar t[MAXL];
b[0]=1;c[0]=1;
for(i=1;i<n;i++){b[i]=0;c[i]=0;};
lc=0;m=-1;
for(i=0;i<n;i++) {
d=s[i];
for(j=1;j<=lc;j++) { d ^=s[i-j] & c[j]; }
if(d!=0){
memcpy(t,c,n);
for(j=0;j<n-i+m;j++) { c[i-m+j]^=b[j]; }
if(2*lc<=i) {
lc=i+1-lc;
m=i;
memcpy(b,t,n);
}
}
}
return lc;
}
int main()
{
int n;
int lc;
char c;
int i,j;
uchar s[MAXL];
uchar ans_s[MAXL];
int ans_lc;
int ans_j;
//if you would like to read the sequence from file, please uncomment the follows line.
//freopen ("s1.txt","r",stdin);
//skip the first line
while((c=getchar())!='\n');
//read the sequence
n=0;
while(n<MAXL){
c=getchar();
//the line should be ended with '\n' or ']'.
if(c=='\n' || c==']') break;
//only '0' and '1' are captured.
if(c>='0' && c<='1') {
//convert '0' and '1' to 0 and 1.
s[n++]=c-'0';
}
}
prints(s,n);
printf("There are %d bits.\n", n);
lc = bm(s,n);
printf("The original LC is %d\n", lc);
//make sure that current ans_lc is big enough.
ans_lc=n; ans_j=-1;
for(i=0;i<n;i++) {
s[i] ^=1;
lc=bm(s,n);
if(lc<ans_lc) {
//save the current optimal answer;
ans_lc=lc; ans_j=i;
memcpy(ans_s,s,n);
printf("Update ans with lc=%d when s[%u]:%u->%u.\n",
ans_lc, ans_j, s[ans_j]^1, ans_s[ans_j]);
}
s[i] ^=1;
}
printf("The minimal 1+lc is %d when s[%u]:%u->%u.\n",
1+ans_lc, ans_j, s[ans_j], ans_s[ans_j]);
prints(ans_s,n);
return 0;
}这是基于C语言实现的wiki上二元序列的线性复杂度，如果需要对应的极小多项式可以从最后的c变量数组中直接转换过来，这并不是什么有难度的事情。
