dict.cpp

设∑＝{α1, α2…… αn }是n个互不相同的符号组成的符号集。 Lk＝{β1β2…βk | βi&#1028 ∑,1≤i≤k}是∑中字符组成的长度为k 的全体字符串。 S是Lk的子集

#include<iostream>

using namespace std;

//n表示n个互不相同的符号，k表示字符串的长度,total_size记录解空间的大小
//S_size记录集合S的大小，best记录最后得到的集合S的大小
int total_size,S_size,*s,k,n,best=0;

//将n进制数转换为十进制数
int change_n_to_ten(int *tmp2)
{
	int x=tmp2[1];
	for(int j=2;j<=k;j++)
    {
		x*=n;
		x+=tmp2[j];
	}
	return x;
}


//判断字符串a和b是否会产生跟原先集合中的串或跟a或b本身重复的串，如果会返回true，否则返回false
bool S_ok(int a,int b)
{	
	int c,d;
    c=a;d=b;
	int ten,*tmp2,*tmp1,j3,j,j2;
	tmp2=new int[k+1];//待加入集合的字符串
	tmp1=new int[2*k+1];//
	for( j=0;j<k;j++)//将a和b转换为k位n进制数，保存在数组tmp1中
	{
		tmp1[k-j]=a%n;
		a/=n;
		tmp1[2*k-j]=b%n;
		b/=n;
	}
	for(j=2;j<=k;j++)//根据规则产生k-1个长度为k的字符串
	{
		for( j2=0;j2<k;j2++)//将产生的字符串复制到数组tmp2中
	    	tmp2[j2+1]=tmp1[j+j2];
		ten=change_n_to_ten(tmp2);//将数组tmp2中的字符串转换为十进制数

		//判断根据规则产生的新字符串是否与原先集合中的字符串重复
        for(j3=1;j3<=S_size;j3++)//S_size表示当前集合中的字符串个数
		{
		  if(ten==s[j3])//重复
		  {
			  delete [] tmp2;
	          delete [] tmp1;
			  return true;
		  }
		  //else j3++;
		}
		//下面两种为跟产生新字符串的两个串c或d重复
		if(ten==c) //
			{
			  delete [] tmp2;
	          delete [] tmp1;
			  return true;
		  }
		if(ten==d) //
			{
			  delete [] tmp2;
	          delete [] tmp1;
			  return true;
		  }
	}
	delete [] tmp2;
	delete [] tmp1;
	return false;
	
}


//判断串i是否能加入集合s，如果可以返回true，否则返回false
bool OK(int i)
{
	int j1,j2;
	for(j1=1;j1<=S_size;j1++)
	{
		if(S_ok(s[j1],i)||S_ok(i,s[j1])) return false;
		for(j2=j1+1;j2<=S_size;j2++)
			if(S_ok(s[j1],s[j2])||S_ok(s[j2],s[j1])) return false;
	}
	return true;
}

//遍历所有可能情况，获得最大的S_size
void search()
{
	for(int j=0;j<=total_size;j++)//total_size等于n的k次方-1
	{
		s[1]=j;
		S_size=1;
		for(int j2=0;j2<=total_size;j2++)
			if((j!=j2)&&OK(j2))
			{
				S_size++;
				s[S_size]=j2;
			}
		if(S_size>best) best=S_size;
	}
}

/*int search(int dep)
{
	
	if(dep>total_size)
	{
		if(S_size>best) best=S_size;
		return 0;
	}

	if(OK(dep))
	{
		S_size++;
		s[S_size]=dep;
		cout<<"dep="<<dep<<endl;
		search(dep+1);
		S_size--;
	}
	search(dep+1);

}*/

int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	cin>>n>>k;
    total_size=1;
	for(int i=1;i<=k;i++) total_size*=n;
	total_size-=1;
	s=new int[total_size+2];
	S_size=1;
	search();
	cout<<best<<endl;
	return 0;
}