AK串II题解（爱思创平台）-创新互联

AKAAKAKAKKAAKK…如果我们在键盘上打出一个AK串（只由字符A和K组成的固定位数的字符串），就可以AK全场么？

不可以，有些AK串不允许出现！

现在给定整数n和m，n表示AK串的位数，m表示所有n位AK串中不允许出现的前缀，请输出合法的n位AK串的个数。

我们可以把AK串看成一个二进制串，比如：AKAKAAKK=10101100

这里就是把A看成1，把K看成0（下面的代码也是这样定义的）

n位二进制串的个数是 2ⁿ

现在，我们就把问题拆成了几个小问题：

1. 如何把AK串转换成二进制串

2.如何判断这个二进制串（也就是被处理后的AK串）是否包含不允许出现的AK串

int tran(string s){int len=s.size();
	int num=0;
	for(int i=0;inum<<=1;
		if(s[i]=='A') {//A为1,K为0
			num+=1;
		}
	}
	num<<=(n-len);//除了1以外的字符都是K也就是0
	return num;//返回构造好的二进制串
}

int check(int x){//判断这个串里是否包含被禁止的子串 
	for(int i=1;i<=m;i++){int k=len[i];
		int y=x&(((1<

#includeusing namespace std;
int n,m;
int ft[20],len[20];
int tran(string s){int len=s.size();
	int num=0;
	for(int i=0;inum<<=1;
		if(s[i]=='A') {//A为1,K为0
			num+=1;
		}
	}
	num<<=(n-len);//除了1以外的字符都是K也就是0
	return num;//返回构造好的二进制 
}
int check(int x){//判断这个串里是否包含被禁止的子串 
	for(int i=1;i<=m;i++){int k=len[i];
		int y=x&(((1<string s;
	cin>>n>>m;
	for(int i=1;i<=m;i++){cin>>s;
		ft[i]=tran(s);//将AK串s转成对应前缀的二进制 
		len[i]=s.size();
		
	} 
	int ans=0;
	int u=1<if(check(i)){//判断i的前缀会不会被禁止 
			ans++;
		}
	}
	cout<