chx简单概况一下题意
给定一个母串S与其子串T ，要将T放入母串中 ，在允许相互覆盖或者相交的情况下 ，问这些子串在母串中覆盖的字符 最多/少 是多少
分析
看见最值很容易就往dp上想，但是这题直接dp会有后效性，就是每个串放的位置没有顺序。但是子串个数非常小，因此可以 $O(n!)$ 的时间枚举放置顺序，这样就消除了dp的后效性。
考虑两个字符串是否相覆盖。假如相覆盖，那么其实就是等价于不放那个被覆盖掉的字符串，而被谁覆盖其实并不重要，因为只需要知道这个串对答案的贡献为零即可，因此可以用 $O(2^n)$ 的时间来枚举每个串是否被覆盖，然后写一个函数判覆盖是否合法即可。
状态设计
阶段性和相覆盖的情况已经枚举过了，剩下的字符串就是要么相交要么不交了（反正不会相覆盖了），那么当前这个串对答案的贡献只与上一个串有关了，那么可以设计dp状态：
$f[i][j]$ 表示强制第 $i$ 个串放在 $j$ 上覆盖字符个数的最大值
$g[i][j]$ 表示强制第 $i$ 个串放在 $j$ 上覆盖字符个数的最小值
转移方程
分两种情况来考虑：
① 与上一个字符串有交
② 与上一个字符串无交
首先设上一个字符串的头的位置是 $k$ , 那么上一个串的结尾位置就是 $k+len_{i-1}-1$ 。当前这个字符串的头的位置是 $j$ , 结尾位置是 $j+len_i-1$ 。若两串有交就意味着
$$\left\{ \begin{aligned} j ≤ k+len_{i-1}-1 \\ k+len_{i-1}-1 < j+len_i-1 \\ j > k \end{aligned} \right.$$$$j-len_{i-1}+1 ≤ k ≤ min(j-1,j+len_i-len_{i-1})$$解出来就是
$$f[i][j]=min_{j-len_{i-1}+1 ≤ k ≤ min(j-1,j+len_i-len_{i-1})}(f[i-1][k]+j+len_i-1-k-len_{i-1}+1)$$$$g[i][j]=max_{j-len_{i-1}+1 ≤ k ≤ min(j-1,j+len_i-len_{i-1})}(g[i-1][k]+j+len_i-1-k-len_{i-1}+1)$$于是就有转移方程
不难发现这个很像一个定长的区间在左右滑动，那就用单调队列优化一下，单调队列里记得是 $f[i-1][j]-j$ 与 $g[i-1][j]-j$ 即可。
$$f[i][j]=min_{k<j-len_{i-1}+1}(f[i-1][k]+len_i)$$$$g[i][j]=max_{k<j-len_{i-1}+1}(g[i-1][k]+len_i)$$然后考虑不交的情况 , 如果不交，那么这个串的贡献就是这个串的长度，就有转移方程
发现与上个串的末位置无关了，那么就用一个前缀最小最大值来优化即可
转移的时间复杂度是 $O(nL)$ 的， 所以总的时间复杂度是 $O(2^n \ n! \ nL)$
代码
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))f^=(ch=='-'),ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?x:-x;
}
const int N=1e4+5;
int n,idx[5];
struct str{
int len,kmp[N];
char S[N];
}s,t[5],tmp[5];
inline int cmp(str x,str y){
return x.len>y.len;
}
inline void getkmp(str &x){
x.kmp[1]=0;
for(int i=2,j=0;i<=x.len;i++){
while(j&&x.S[i]!=x.S[j+1])j=x.kmp[j];
x.kmp[i]=(j+=(x.S[i]==x.S[j+1]));
}
}
inline int check(str s1,str s2){ //s1 <- s2
int j=0;
for(int i=1;i<=s1.len;i++){
while(j&&s1.S[i]!=s2.S[j+1])j=s2.kmp[j];
if(s1.S[i]==s2.S[j+1])j+=1;
if(j==s2.len)return 1;
}
return 0;
}
inline int lowbit(int x){
return x&-x;
}
inline int cnt(int x){
int ret=0;
while(x){
x-=lowbit(x);
ret+=1;
}
return ret;
}
int tag[5][N],use[5],minans=1e9,maxans=-1e9;
int f[5][N],g[5][N],maxhd,maxtl,minhd,mintl,qmax[N],qmin[N],premax,premin;
int fuck[5][5];
void trans(int j){
int premin=1e9,premax=-1e9,now=1;
int len1=tmp[j].len,len2=tmp[j-1].len;
minhd=maxhd=1;
mintl=maxtl=0;
for(int i=1;i<=s.len;i++){
int l=i-len2+1,r=min(i-1,i+len1-len2);
while(minhd<=mintl&&qmin[minhd]<l)
premin=min(premin,f[j-1][qmin[minhd++]]);
while(maxhd<=maxtl&&qmax[maxhd]<l)
premax=max(premax,g[j-1][qmax[maxhd++]]);
for(;now<=r;now++){
while(minhd<=mintl&&f[j-1][qmin[mintl]]-qmin[mintl]>=f[j-1][now]-now)mintl--;
while(maxhd<=maxtl&&g[j-1][qmax[maxtl]]-qmax[maxtl]<=g[j-1][now]-now)maxtl--;
qmin[++mintl]=now;
qmax[++maxtl]=now;
}
if(tag[j][i]){
f[j][i]=premin+len1;
g[j][i]=premax+len1;
if(minhd<=mintl){
int k=qmin[minhd];
f[j][i]=min(f[j][i],f[j-1][k]-k+i-len2+len1);
}
if(maxhd<=maxtl){
int k=qmax[maxhd];
g[j][i]=max(g[j][i],g[j-1][k]-k+i-len2+len1);
}
}
}
}
void search(int Sq,int lar){
for(int i=1,j=1;i<=lar,j<=n;j++){
if((Sq>>(j-1))&1){
tmp[idx[j]]=t[j];
}
}
memset(f,0x3f,sizeof(f));
memset(g,-0x3f,sizeof(g));
memset(tag,0,sizeof(tag));
for(int k=1;k<=lar;k++){
int now=0;
for(int i=1;i<=s.len;i++){
while(now&&tmp[k].S[now+1]!=s.S[i])now=tmp[k].kmp[now];
if(tmp[k].S[now+1]==s.S[i])now++;
if(now==tmp[k].len){
tag[k][i-tmp[k].len+1]=1;
now=tmp[k].kmp[now];
}
}
}
for(int i=1;i<=s.len;i++){
if(tag[1][i]){
f[1][i]=tmp[1].len;
g[1][i]=tmp[1].len;
}
}
for(int j=2;j<=lar;j++){
trans(j);
}
for(int i=1;i<=s.len;i++){
minans=min(minans,f[lar][i]);
maxans=max(maxans,g[lar][i]);
}
}
void dfs(int ok,int up,int Sq){
//S表示状态 up表示枚举上限
if(ok>n){
search(Sq,up);
return;
}
else{
if((Sq>>(ok-1))&1){
for(int i=1;i<=up;i++){
if(!use[i]){
use[i]=1;
idx[ok]=i;
dfs(ok+1,up,Sq);
use[i]=0;
}
}
}
else dfs(ok+1,up,Sq);
}
}
inline void solve(){
minans=1e9;
maxans=-1e9;
scanf("%s",s.S+1);
s.len=strlen(s.S+1);
getkmp(s);
n=read();
for(int i=1;i<=n;i++){
scanf("%s",t[i].S+1);
t[i].len=strlen(t[i].S+1);
getkmp(t[i]);
}
sort(t+1,t+n+1,cmp);
memset(fuck,0,sizeof(fuck));
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(check(t[j],t[i]))fuck[j][i]=1;
}
}
for(int ss=0;ss<(1<<n);ss++){
int flg=1;
for(int i=1;i<=n;i++){
if(!(1&(ss>>i-1))){
int shabi=1;
for(int j=1;j<i;j++){
if((1&(ss>>j-1))&&fuck[j][i]){
shabi=0;
break;
}
}
if(shabi)flg=0;
}
}
if(flg)dfs(1,cnt(ss),ss);
}
printf("%lld %lld\n",minans,maxans);
}
signed main(){
int T=read();
while(T--)solve();
}