先用KMP求出所有可以放的位置，然后两个值分别处理。
最大值：
贪心，4!枚举放的先后位置顺序，2^3枚举相邻两个串是否有交。
若有交，则后一个的起始位置一定是离前一个的结束位置最近的位置，无交也一样。
最小值：
首先去掉被其它串包含的串，因为肯定可以和其它串放同样的位置。
将所有串从长到短排序方便DP。
f[S][i]表示当前放的串的情况为S，串目前所覆盖到的最后一个位置为i，覆盖的最小总长度是多少，则有：
当最后一个覆盖到i的串位置与其它串不相交时：f[S][i]=min{f[S'][k]} 这个用一个前缀和优化即可。
当相交时：f[S][i]=min(f[S'][j]+i-j) 因为串已经从长到短排好序了所有没有问题。这个用单调队列优化即可。
写的龟速，跑得飞快。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mem(a) memset(a,0,sizeof(a))
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
char s[][N],A[N];
bool b[],fl[][N];
int T,n,len,L[],pos[][N],num[],nxt[N],p[],st[],ed[],f[][N],g[][N],q[][N]; void KMP(char S[],char T[],int pos[],int &num,bool fl[]){
int n=strlen(T+),m=strlen(S+),j=; nxt[]=;
rep(i,,m){
while (j && S[j+]!=S[i]) j=nxt[j];
if (S[j+]==S[i]) nxt[i]=++j; else nxt[i]=;
}
j=; num=;
rep(i,,n){
while (j && S[j+]!=T[i]) j=nxt[j];
if (S[j+]==T[i]) j++;
if (j==m) pos[++num]=i-m+,fl[i]=,j=nxt[j];
}
} bool chk(char S[],char T[]){
int n=strlen(T+),m=strlen(S+);
rep(i,,n-m+){
bool flag=;
rep(j,,m) if (S[j]!=T[i+j-]){ flag=; break; }
if (!flag) return ;
}
return ;
} void solve_max(){
rep(i,,n) p[i]=i; int ans=; mem(fl);
do{
for (int S=; S<<<(n-); S++){
int x=pos[p[]][]+L[p[]]-,res=L[p[]]; ans=max(ans,res); bool flag=;
rep(i,,n){
int d=upper_bound(pos[p[i]]+,pos[p[i]]+num[p[i]]+,x)-pos[p[i]];
if (S&(<<(i-))){
if (d<=num[p[i]] && pos[p[i]][d]>x) res+=L[p[i]],x=pos[p[i]][d]+L[p[i]]-;
else{ flag=; break; }
}else{
d--;
if (d && pos[p[i]][d]<=x) res+=L[p[i]]-(x-pos[p[i]][d]+),x=pos[p[i]][d]+L[p[i]]-;
else{ flag=; break; }
}
if (!flag) ans=max(ans,res);
}
}
}while (next_permutation(p+,p+n+));
printf("%d\n",ans);
} void solve_min(){
int S0=(<<n)-;
rep(i,,n-) rep(j,i+,n) if (!b[j] && chk(s[j],s[i])) b[j]=,S0^=<<(j-);
memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g));
mem(f[]); mem(g[]);
rep(i,,(<<n)-) st[i]=,ed[i]=;
rep(i,,len){
for (int S=; S<<<n; S++){
if (S&(S^S0)) continue; g[S][i]=g[S][i-];
rep(j,,n) if (S&(<<(j-)) && fl[j][i]){
int S1=S^(<<(j-));
if (i-L[j]>=) f[S][i]=min(f[S][i],g[S1][i-L[j]]+L[j]);
while (st[S1]<=ed[S1] && q[S1][st[S1]]<=i-L[j]) st[S1]++;
if (st[S1]<=ed[S1]) f[S][i]=min(f[S][i],f[S1][q[S1][st[S1]]]+i-q[S1][st[S1]]);
while (st[S]<=ed[S] && f[S][q[S][ed[S]]]-q[S][ed[S]]>=f[S][i]-i) ed[S]--;
q[S][++ed[S]]=i; g[S][i]=min(g[S][i-],f[S][i]);
}
}
}
printf("%d ",g[S0][len]);
} int main(){
freopen("bzoj4560.in","r",stdin);
freopen("bzoj4560.out","w",stdout);
for (scanf("%d",&T); T--; ){
mem(fl); mem(b); scanf("%s",A+); len=strlen(A+); scanf("%d",&n);
rep(i,,n) scanf("%s",s[i]+),L[i]=strlen(s[i]+);
rep(i,,n-) rep(j,i+,n) if (L[i]<L[j]) swap(s[i],s[j]),swap(L[i],L[j]);
rep(i,,n) KMP(s[i],A,pos[i],num[i],fl[i]);
solve_min(); solve_max();
}
return ;
}