#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变量数组中直接转换过来，这并不是什么有难度的事情。