记录编号	489501	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 1997]文件匹配	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.567 s
提交时间	2018-03-03 00:13:44	内存使用	3.45 MiB

#include<bits/stdc++.h>
using namespace std;
#define reg register
int vis[30],Time,Set[30];
char id[110],go[30][63],s,t,now,length;
void init(){
	length=0;
	while (now) --now,memset(go[now],0,sizeof go[now]);
	s=t=++now;
}
inline void insert(reg char s,reg char t,reg char c){
	go[s][c]=t;
}
inline void insert_star(reg char s,reg char t){
	reg char a=++now;
	go[s][0]=a;
	memset(go[a]+1,a,62);
	go[a][0]=t;
}
inline void insert_question(reg char s,reg char t){
	memset(go[s]+1,t,62);
}
inline void append(reg char c){
	reg int last=t;
	t=++now;
	length+=(c!='*');
	if (c=='?') insert_question(last,t);
	else if (c=='*') insert_star(last,t);
	else insert(last,t,id[c]);
}
void regex_expression(reg char *S){
	init();
	for (reg char c=*S;c;c=*++S) append(c);
	for (int i=0;i<=now;i++){
		++Time;
		Set[i]=0;
		for (int j=i;vis[j]!=Time;vis[j]=Time,Set[i]|=1<<j,j=go[j][0]);
	}
}
int Sa,Sb;
int match(reg char *T){
	Sa=Set[s];
	for (reg char c=*T;c;c=*++T){
		reg char w=id[c];
		Sb=0;
		for (int i=1;i<=now;i++)
			if (Sa>>i&1) Sb|=Set[go[i][w]];
		Sa=Sb;
	}
	return Sa>>t&1;
}
const int N=260;
int n,m,tp[N],lenS[N],lenT[N];
char S[N][10],T[N][10];
int count(reg char *pattern){
	regex_expression(pattern);
	for (reg int i=1;i<=m;i++)
		if (lenT[i]>=length&&match(T[i])) return -1e9;
	reg int ans=0;
	for (reg int i=1;i<=n;i++)
		if (lenS[i]>=length) ans+=match(S[i]);
	return ans;
}
int count_without_limit(reg char *pattern){
	regex_expression(pattern);
	reg int ans=0;
	for (reg int i=1;i<=n;i++)
		if (lenS[i]>=length) ans+=match(S[i]);
	return ans;
}
char ans[20];
int Ans,len;
void dfs(reg char *s){
	reg int n=strlen(s);
	s[n]='*';
	reg int cnt=count_without_limit(s);
	s[n]=0;
	if (cnt<Ans||(cnt==Ans&&n>=len)) return;
	cnt=count(s);
	if (cnt>Ans||(cnt==Ans&&n<len)) memcpy(ans,s,20),len=n,Ans=cnt;
	static char stack_pool[20][20];
	reg char *t=stack_pool[n];
	memcpy(t,s,20);
	t[n]='?';dfs(t);
	if (s[n-1]!='*'&&s[n-1]!='?') t[n]='*',dfs(t);
	for (t[n]='a';t[n]<='z';++t[n]) dfs(t);
	for (t[n]='A';t[n]<='Z';++t[n]) dfs(t);
	for (t[n]='0';t[n]<='9';++t[n]) dfs(t);
}
void sort(int n,char S[][10],int *lenS){
	for (int i=1;i<=n;i++)
	for (int j=i;j<=n;j++)
	if (lenS[i]<lenS[j]){
		swap(lenS[i],lenS[j]);
		static char str[10];
		memcpy(str,S[i],10);
		memcpy(S[i],S[j],10);
		memcpy(S[j],str,10);
	}
}
int main()
{
	freopen("wildcard.in","r",stdin);
	freopen("wildcard.out","w",stdout);
	for (int i='a';i<='z';i++) id[i]=i-'a'+1;
	for (int i='A';i<='Z';i++) id[i]=i-'A'+27;
	for (int i='0';i<='9';i++) id[i]=i-'0'+53;
	char str[10],c[5];
	while (~scanf("%s",str)){
		scanf("%s",c);
		if (c[0]=='+') memcpy(S[++n],str,10);
			else memcpy(T[++m],str,10);
	}
	for (int i=1;i<=n;i++) lenS[i]=strlen(S[i]);
	for (int i=1;i<=m;i++) lenT[i]=strlen(T[i]);
	sort(n,S,lenS);
	sort(m,T,lenT);
	char *s=new char[20];
	memset(s,0,20);
	dfs(s);
	printf("%d\n%s\n",Ans,ans);
	return 0;
}