记录编号	407610	评测结果	AAAAAAAAAA
题目名称	子串	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2017-05-22 13:37:51	内存使用	0.89 MiB

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1010;
int next[maxn][63]={0},fail[maxn]={0},b[maxn]={0},ind[256]={0},cnt=1;
char s[30][30];
double r[63];
int n;
void insert(char *s){
	int len=strlen(s);
	int p=0;
	for(int i=0;i<len;i++){
		int c=ind[s[i]];
		if(!next[p][c]){
			b[cnt]=0;
			next[p][c]=cnt;
			cnt++;//wtf
		}
		p=next[p][c];
	}
	b[p]=1;
}
void build(){
	queue<int>q;
	fail[0]=0;
	for(int i=0;i<63;i++){
		if(next[0][i]){
			fail[next[0][i]]=0;
			q.push(next[0][i]);
		}
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<63;i++){
			if(!next[x][i]){
				next[x][i]=next[fail[x]][i];
				continue;
			}
			q.push(next[x][i]);
			int p=fail[x];
			while(p&&!next[p][i])p=fail[p];
			fail[next[x][i]]=next[p][i];
			b[next[x][i]]|=b[fail[next[x][i]]];
		}
	}
}
double w[maxn][105]={0};
int vis[maxn][105]={0};
double getnum(int x,int l){
	if(!l)return 1.0;
	if(vis[x][l])return w[x][l];
	vis[x][l]=1;
	double& ans=w[x][l];
	ans=0.0;
	for(int i=0;i<n;i++)
		if(!b[next[x][i]])ans+=r[i]*getnum(next[x][i],l-1);
	return ans;
}
int work(){
	freopen("substrings.in","r",stdin);
	freopen("substrings.out","w",stdout);
	int t;
	scanf("%d",&t);
	for(int ca=1;ca<=t;ca++){
		memset(vis,0,sizeof(vis));
		memset(w,0,sizeof(w));
		memset(ind,0,sizeof(ind));
		memset(next,0,sizeof(next));
		memset(fail,0,sizeof(fail));
		memset(b,0,sizeof(b));
		cnt=1;
		int k,l;
		char A;
		scanf("%d",&k);
		for(int i=0;i<k;i++){
			scanf("%s",s[i]);
		}
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			cin>>A;
			scanf("%lf",&r[i]);
			//printf("%d\n",A);
			ind[A]=i;
		}
		for(int i=0;i<k;i++)insert(s[i]);
		build();
		scanf("%d",&l);
		double ans=getnum(0,l);
		printf("Case #%d: %.6lf\n",ca,ans);
	}
	return 0;
}
int sh=work();
int main(){
	return 0;
}