1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分4秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<queue> 25 #define LL long long 26 #define maxn 20000 27 using namespace std; 28  29 int n,m; 30 char str[55][1110][55]; 31 struct Trie 32 { 33     int next[maxn][26],fail[maxn],end[maxn]; 34     int root,L; 35     int newnode() 36     { 37         memset(next[L],-1,sizeof(next[L])); 38         end[L++] = 0; 39         return L-1; 40     } 41     void init() 42     { 43         L = 0; 44         root = newnode(); 45     } 46     void insert(char buf[],int id) 47     { 48         int len = strlen(buf); 49         int now = root; 50         for(int i = 0;i < len ;i++) 51         { 52             if(next[now][buf[i]-‘a‘] == -1) 53             { 54                 next[now][buf[i]-‘a‘] = newnode(); 55             } 56             now = next[now][buf[i]-‘a‘]; 57         } 58         end[now] = id; 59     } 60     void build() 61     { 62         queue<int>Q; 63         fail[root] = root; 64         for(int i = 0;i < 26;i++) 65             if(next[root][i] == -1) 66                 next[root][i] = root; 67             else 68             { 69                 fail[next[root][i]] = root; 70                 Q.push(next[root][i]); 71             } 72         while( !Q.empty() ) 73         { 74             int now = Q.front(); 75             Q.pop(); 76             if(end[fail[now]] == -1)end[now] = -1; 77             else end[now] |= end[fail[now]]; 78             for(int i = 0;i < 26;i++) 79                 if(next[now][i] == -1) 80                     next[now][i] = next[fail[now]][i]; 81                 else 82                 { 83                     fail[next[now][i]] = next[fail[now]][i]; 84                     Q.push(next[now][i]); 85                 } 86         } 87     } 88     int cmp(char str1[],char str2[]) 89     { 90         if(strlen(str1) < strlen(str2)) 91         { 92             return 1;  93         }else if(strlen(str1) > strlen(str2)){ 94             return 0 ; 95         }else{ 96             if(strcmp(str1,str2) < 0) 97                 return 1; 98         } 99         return 0;100     }101     int dp[100][maxn];102     void solve()103     {104         memset(dp,-1,sizeof(dp));105         dp[0][0] = 0 ; 106         int ai = 0 ; 107         int aj = 0 ;108         int mx = 0;109         char tmp[55];110         char ans[55];111         strcpy(ans,"");112         strcpy(str[0][0],"");113         for(int i = 0 ;i < n;i ++)114         {115             for(int j =0 ;j < L ;j ++)116             {117                 if(dp[i][j] != -1 )118                 {119                     strcpy(tmp,str[i][j]);120                     int len = strlen(str[i][j]);121 122                     for(int s = 0 ;s < 26 ;s ++)123                     {124                         int nex = next[j][s];125                         tmp[len] = ‘a‘ + s;126                         tmp[len + 1] = 0;127                         int tt = dp[i][j];128 129                         if(end[nex] != -1)130                             tt += end[nex];131 132                         if(tt > dp[i+1][nex] ||(tt == dp[i+1][nex] && cmp(tmp,str[i+1][nex]) ))133                         {134                             dp[i+1][nex] = tt;135                             strcpy(str[i+1][nex],tmp);136                             if(tt > mx ||(tt == mx && cmp(tmp,ans)))137                             {138                                 mx = tt; 139                                 strcpy(ans,tmp);140                                 //printf("%s %d\n",ans,mx);141                             }142                         }143                     }144                 }145             }146         }147         printf("%s\n",ans);148     }149 150 };151 152 Trie ac;153 char tstr[205][20];154 int main(){155     int t; 156     scanf("%d",&t);157     while(t--)158     {159         scanf("%d %d",&n,&m);160         ac.init();161         for(int i = 1;i <= m ;i ++ )162         {163             scanf("%s",tstr[i]);164         }165         int temp ; 166         for(int i = 1; i <= m;i ++)167         {168             scanf("%d",&temp);169             ac.insert(tstr[i],temp) ;  170         }171         ac.build();172         ac.solve();173     }174     return 0;175 }