Berlekamp-Massey算法

#include 
#include 
#include 
int *BM（int*aint N）
{
	int i=0j=0ff=0ll=1m=0k=0s=0;
	int **f;
	int *l*d*r;
	f=（int**）malloc（N*sizeof（int））;
	l=（int*）malloc（N*sizeof（int））;
	d=（int*）malloc（N*sizeof（int））;
	r=（int*）malloc（（N+1）*sizeof（int））;
	for （j=0;j	{
		f[j]=（int*）malloc（N*sizeof（int））;
	}
	//初始化
	for （i=0;i	{
		for （j=0;j		{
			f[i][j]=0;
		}
	}
	//寻找第一位不为0的比特
	if （a[0]==1）
	{
		ff=1;
		ll=0;
	} 
	else
	{
		for （i=0;i<=N;i++）
		{
			if （a[i]==1）
			{
				for （j=0;j				{
					f[j][0]=1;
					l[j]=0;
				}
				m=i;
				i=N+1;
			}
		}
	}
	f[m][m+1]=1;
	f[m][0]=1;
	l[m]=m+1;
	//循环
	for （i=m+1;i	{
		//计算dn
		d[i]=0;
		for （j=0;j<=l[i-1]-1;j++）
		{
			d[i]=d[i]+f[i-1][j]*a[i-l[i-1]+j];
		}
		d[i]=（a[i]+d[i]）%2;
		//根据dn的取值，计算fn及ln
		if （d[i]==0）
		{
			for （j=0;j			{
				f[i][j]=f[i-1][j];
			}
			l[i]=l[i-1];
		} 
		else
		{
			//寻找满足条件的ls
			for （j=i-1;j>0;j--）
			{
				if （l[j]>l[j-1]）
				{
					s=j;
					j=0;
				}
			}
			//计算k
			k=abs（s-l[s-1]-（i-l[i-1]））;
			if （s-l[s-1]>=i-l[i-1]）
			{
				for （j=0;j				{
					if （f[s-1][j]==1）
					{
						f[i][j+k]++;
					}
				}
				for （j=0;j				{
					f[i][j]=abs（（f[i-1][j]+f[i][j]）%2）;
				}
				l[i]=l[i-1];
			} 
			else
			{
				for （j=0;j				{
					if （f[i-1][j]==1）
					{
						f[i][j+k]++;
					}
				}
				for （j=0;j				{
					f[i][j]=abs（（f[s-1][j]+f[i][j]）%2）;
				}
				l[i]=l[i-1]+k;
			}
		}
	}
	for （i=0;i	{
		r[i]=f[N-1][i];
	}
	r[N]=l[N-1];
	return（r）;
}
void main（）
{//获取数据
	int a[1000];
	int i=0;
	int N=0;
	int *r;
	FILE *out;
	out=fopen（“结果.txt““w“）;
	fclose（out）;
	out=fopen（“结果.txt““a+“）;
	printf（“请输入数据\n“）;
	for （i=0;i<1000;i++）
	{
		scanf（“%c“&a[i]）;
		a[i]=（a[i]%45）+1;
		if （a[i]!=0 && a[i]!=1）break;			
	}
	N=i;
	r=BM（aN）;
	//输出
	printf（“线性复杂度为：%d\n“r[N]）;
	fprintf（out“线性复杂度为：%d\n“r[N]）;
	printf（“极小多项式为：“）;
	fprintf（out“极小多项式为：“）;
	for（i=N-1;i>0;i--）
	{
		if（r[i]==1）
		{
			printf（“x^%d+“i）;
			fprintf（out“x^%d+“i）;
		}
	}
	if（r[0]==1）
	{
		printf（“1\n“）;
		fprintf（out“1\n“）;
	}
}