Berlekamp-Massey算法

Berlekamp-Massey算法#includeiostream#includestring#includefstream//#includemath.husingnamespacestd;intN0(stringa);intmain(){stringa;intn0,N;//n0为第一个不为0的数intsum,t;intdn;inti,j,n,m,k;ints=0;intA[1002];intu=0;longintf1[2000]={0};//上一次的极小多项式longintf2[2000]={0};//l[n]变化前的极小多项式longintfn[2000]={0};intLL=0;intl[1002]={0};fstreamp(d:\\xulie200.txt,ios::in);//读入apa;n0=N0(a);N=a.size();n=n0;f2[0]=1;f1[n0+1]=1;f1[0]=1;l[n0+1]=n0+1;//coutn0endl;for(i=0;i=N-1;i++)//将a的值赋予数组A{A[i]=a[i]-'0';}coutendl;//开始循环递归for(n=n0+1;n=N-1;n++){dn=0;dn=dn^A[n];for(i=0;i=l[n]-1;i++){dn=dn^(A[n-l[n]+i]*f1[i]);}if(dn==0){for(i=0;i=l[n];i++){fn[i]=f1[i];}l[n+1]=l[n];}else{intg[2000]={0};for(j=n;j=n0+1;j--)//找到m{//if(j=1)//{if(l[j]!=l[j-1]){m=j-1;break;}//}//else//{//if(l[j]!=LL)//{//m=j;//break;//}}if(m-l[m]=n-l[n]){k=(m-l[m])-(n-l[n]);for(i=0;i=l[n];i++){g[i+k]=f2[i];}for(i=0;i=l[n]+50;i++){fn[i]=f1[i]^g[i];}l[n+1]=l[n];}else{k=(n-l[n])-(m-l[m]);for(i=0;i=l[n]+50;i++){g[i+k]=f1[i];}for(i=0;i=l[n]+50;i++){fn[i]=f2[i]^g[i];}l[n+1]=k+l[n];}}if(l[n+1]!=l[n]){for(j=0;j=l[n]+50;j++){f2[j]=f1[j];u++;}}for(i=0;i=l[n]+50;i++){f1[i]=fn[i];}}cout极小多项式为:endl;sum=0;coutx^l[n];for(i=l[n]-1;i0;i--){//coutfn[i];if(fn[i]!=0){cout+x^i;sum++;}}if(fn[0]!=0){cout+fn[0]endl;}cout线性复杂度为：l[n]endl;return0;}intN0(stringa)//计算a的第一位不为0的位置{intn0,N;inti;N=a.size();for(i=0;i=N;i++){if(a[i]!='0'){n0=i;break;}}returnn0;}