题目是给几个带有价值的单词。而一个字符串的价值是 各单词在它里面出现次数*单词价值 的和，问长度不超过n的最大价值的字符串是什么？
依然是入门的AC自动机+DP题。。不一样的是这题要输出具体方案，加个字符数组记录每个状态最优情况的字符串即可。
另外题目字典序是先考虑长度再考虑每一位单词；特别要注意，有一个非常坑的地方看了Disscus才知道——单词A包含单词B，那么只计算单词A不计算单词B。
- dp[i][j]表示长度i（自动机上转移k步）后缀状态是自动机第j个结点的字符串的最大价值
- dp[0][0]=0
- 我为人人，dp[i][j]向26个字母转移到dp[i'][j']
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int tn,ch[][],fail[],val[];
void insert(char *s,int a){
int x=;
for(int i=; s[i]; ++i){
int y=s[i]-'a';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
val[x]+=a;
}
void init(){
memset(fail,,sizeof(fail));
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=; i<; ++i){
if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i];
else ch[x][i]=ch[fail[x]][i];
//val[ch[x][i]]+=val[ch[fail[x]][i]];
}
}
}
char str[][];
int d[][];
char path[][][];
int main(){
int t,n,m,a;
scanf("%d",&t);
while(t--){
tn=;
memset(ch,,sizeof(ch));
memset(val,,sizeof(val));
scanf("%d%d",&n,&m);
for(int i=; i<m; ++i) scanf("%s",str[i]);
for(int i=; i<m; ++i){
scanf("%d",&a);
insert(str[i],a);
}
init();
memset(path,,sizeof(path));
memset(d,-,sizeof(d));
d[][]=;
for(int i=; i<n; ++i){
for(int j=; j<=tn; ++j){
if(d[i][j]==-) continue;
for(int k=; k<; ++k){
int &nd=d[i+][ch[j][k]];
if(nd<d[i][j]+val[ch[j][k]]){
nd=d[i][j]+val[ch[j][k]];
strcpy(path[i+][ch[j][k]],path[i][j]);
path[i+][ch[j][k]][i]=k+'a';
}else if(nd==d[i][j]+val[ch[j][k]]){
char tmp[]={};
strcpy(tmp,path[i][j]);
tmp[i]=k+'a';
if(strcmp(tmp,path[i+][ch[j][k]])<) strcpy(path[i+][ch[j][k]],tmp);
}
}
}
}
int resi=,resj=;
for(int i=; i<=n; ++i){
for(int j=; j<=tn; ++j){
if(d[resi][resj]<d[i][j]) resi=i,resj=j;
else if(d[resi][resj]==d[i][j] && resi==i && strcmp(path[resi][resj],path[i][j])>) resi=i,resj=j;
}
}
puts(path[resi][resj]);
}
return ;
}