NC20149. [JLOI2016]字符串覆盖
描述
输入描述
第一行包含一个正整数T，表示数据组数。保证T ≤ 10。
接下来依次描述T组数据，每组数据中：
第一行包含一个由小写字母组成的字符串，表示母串A。
第二行包含一个整数N，表示子串的个数。
接下来N行，每行包含一个由小写字母组成的字符串，描述子串。
数据保证所有子串均在母串中出现。字符串长度A ≤ 10000,N ≤ 4,子串长充 ≤ 1000
输出描述
输出为T行，对应每组数据的答案。每行包含两个整数Minans和Maxans，分别表示对应数据中能被覆盖字符数量的最小值和最大值。
示例1
输入:
2 hello 4 he l l o abacaba 4 ab ba a c
输出:
4 5 4 6
C++(clang++ 11.0.1) 解法, 执行用时: 15ms, 内存消耗: 2112K, 提交时间: 2022-12-11 14:45:17
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<stack>
#include<cmath>
using namespace std;
#define Cpp11
#ifdef Cpp11
#define _for(i,a,b) for(auto i = (a);i<(b);++i)
#define _rep(i,a,b) for(auto i = (a);i<=(b);++i)
#define _dep(i,a,b) for(auto i = (a);i>=(b);--i)
#include<ctime>
#include<complex>
#include<random>
#include<chrono>
#include<limits>
#include<complex>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<functional>
#include<bitset>
#define IO ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#endif
#ifndef Cpp11
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rep(i,a,b) for(int i = (a);i<=(b);++i)
#define _dep(i,a,b) for(int i = (a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
#endif
using namespace std;
#define fr first
#define sc second
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sci(x) scanf("%d",&(x))
#define scl(x) scanf("%lld",&(x))
#define debugline fprintf(stderr,"-----------------------\n");
#define szint(x) ((int)(x).size())
#ifdef I128IO
typedef __int128 I128;
char buff[200];
template<typename T>
void read(T& o)
{
o = 0;
scanf("%s",buff);
//printf("%s\n",buff);
T f = 1;
int i = 0;
if(buff[0]=='-')i++,f = -1;
for(;buff[i];++i)
{
o*=10,o+=buff[i]-'0';
}
o*=f;
}
template<typename T>
void write(T o)
{
int len = 0;
buff[0] = '0';
if(o==0)
{
putchar('0');
return;
}
int f = 1;
if(o<0) f = -1;
o*=f;
for(;o;o/=10) buff[len++] = o%10+'0';
if(f==-1) buff[len++] = '-';
reverse(buff,buff+len);
buff[len++] ='\0';
printf("%s",buff);
}
#endif
#ifdef FIO
char buff[100];
template<typename T>
void read(T& o)
{
o = 0;
scanf("%s",buff);
//printf("%s\n",buff);
T f = 1;
int i = 0;
if(buff[0]=='-')i++,f = -1;
for(;buff[i];++i)
{
o*=10,o+=buff[i]-'0';
}
o*=f;
}
template<typename T>
void write(T o)
{
int len = 0;
buff[0] = '0';
if(o==0)
{
putchar('0');
return;
}
int f = 1;
if(o<0) f = -1;
o*=f;
for(;o;o/=10) buff[len++] = o%10+'0';
if(f==-1) buff[len++] = '-';
reverse(buff,buff+len);
buff[len++] ='\0';
printf("%s",buff);
}
#endif
#define _Random_
#ifdef _Random_
mt19937 __MT(chrono::system_clock::now().time_since_epoch().count());
#endif
#ifndef BigNumber
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<LL,LL> pLL;
typedef vector<LL> vL;
typedef vector<vL> vLL;
#endif
#ifdef I128IO
typedef __int128 SPLL;
typedef vector<SPLL> vSPLL;
#endif
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef vector<viii> viiii;
typedef pair<int,int> pii;
#ifdef Cpp11
typedef complex<double> CD;
#endif
const int maxn = 10000+10;
const LL maxm = 4;
const int apsz = 26;
const int inf = 1e9;
const int block = 100;
char A[maxn];
int n,m,S;
int f[maxn];
int has[maxm][maxn];
vi canpos[maxm];
char s[maxm][maxn];
int Len[maxm];
int maxval,minval;
deque<int> q[1<<4];
int pre[maxn][1<<4];
int dp[maxn][1<<4];
void dfs(int d,int preneed,int preend,int tot,vi& vis)
{
//cerr<<d<<" "<<preneed<<" "<<preend<<endl;
if(d==m)
{
maxval = max(maxval,tot);
return;
}
int alltot = tot;
_for(i,0,m)
{
if(vis[i])continue;
alltot = tot;
if(preneed==0)
{
int pt = upper_bound(all(canpos[i]),preend)-canpos[i].begin();
if(pt!=szint(canpos[i]))
{
vis[i] = 1;
int nowend = canpos[i][pt]+Len[i]-1;
alltot+=Len[i];
//cerr<<nowend<<endl;
dfs(d+1,0,nowend,alltot,vis);
dfs(d+1,1,nowend,alltot,vis);
vis[i] = 0;
}
}
else
{
int pt = lower_bound(all(canpos[i]),preend)-canpos[i].begin();
if(pt>0||canpos[i][pt]==preend)
{
if(canpos[i][pt]!=preend)--pt;
int nowend = canpos[i][pt]+Len[i]-1;
alltot = tot+max(nowend-preend,0);
vis[i] = 1;
dfs(d+1,0,max(nowend,preend),alltot,vis);
dfs(d+1,1,max(nowend,preend),alltot,vis);
vis[i] = 0;
}
}
}
}
inline void getFail(char* s,int* f,int len)
{
memset(f,0,sizeof(f));
f[0] = 0;
f[1] = 0;
for(int i = 1;i<len;++i)
{
int j = f[i];
while(j&&s[j]!=s[i])j = f[j];
f[i+1] = s[j]==s[i]?j+1:j;
}
}
inline void match(char* s,char* t,int n,int m,int* f,int* pos)
{
int j = 0;
_for(i,0,n)
{
while(j&&t[j]!=s[i])j = f[j];
if(t[j]==s[i])++j;
if(j==m) pos[i] = 1;
}
}
inline void init()
{
_for(i,0,m)
{
canpos[i].clear();
getFail(s[i],f,Len[i]);
_for(j,0,n)has[i][j] = 0;
match(A,s[i],n,Len[i],f,has[i]);
_for(j,0,n)
{
if(has[i][j])canpos[i].pb(j-Len[i]+1);
}
// _for(j,0,n)
// {
// cerr<<has[i][j]<<" ";
// }
// cerr<<endl;
}
}
inline int cover(int i,int j)
{
if(Len[i]>Len[j])return 0;
string ss,ts;
ss = string(s[i]);
ts = string(s[j]);
if(ts.find(ss)!=string::npos)return 1;
return 0;
}
inline void solve()
{
init();
vi vis(m,0);
dfs(0,0,-1,0,vis);
S = 1<<m;S--;
//cerr<<S<<endl;
_for(i,0,S) q[i].clear();
_for(j,0,m)
{
if((S&(1<<j))==0)continue;
_for(i,0,m)
{
if(i==j)continue;
if((S&(1<<i))==0)continue;
if(cover(i,j))S^=(1<<i);
}
}
//cerr<<S<<endl;
_for(i,0,n)
{
_for(j,0,1<<m)
{
if(j)pre[i][j] = dp[i][j] = inf;
else pre[i][j] = dp[i][j] = 0;
}
}
minval = inf;
_for(i,0,n)
{
if(i)
{
_for(x,0,1<<m)pre[i][x] = pre[i-1][x];
}
for(int x = 0;x<(1<<m);++x)
{
int res = x&S;
if(res!=x)continue;
_for(j,0,m)
{
if((x&(1<<j))&&has[j][i]==1)
{
if(((1<<j)&x)==0)continue;
int y = x^(1<<j);
//cerr<<i<<" "<<j<<endl;
//cerr<<x<<" "<<y<<endl;
int preval;
if(i-Len[j]<0)
{
if(y==0) preval = 0;
else preval = inf;
}
else preval = pre[i-Len[j]][y];
//cerr<<i-Len[j]<<" "<<j<<" "<<y<<" "<<preval<<endl;
dp[i][x] = min(dp[i][x],preval+Len[j]);
for(;!q[y].empty()&&q[y].front()<=i-Len[j];)q[y].pop_front();
if(!q[y].empty())
{
dp[i][x] = min(dp[i][x],dp[q[y].front()][y]-q[y].front()+i);
//cerr<<i<<" "<<dp[i][x]<<endl;
}
for(;!q[x].empty()&&dp[q[x].back()][x]-q[x].back()>=dp[i][x]-i;)
{
q[x].pop_back();
}
q[x].pb(i);
if(i)pre[i][x] = min(pre[i-1][x],dp[i][x]);
else pre[i][x] = dp[i][x];
}
}
}
}
minval = pre[n-1][S];
assert(minval<inf);
printf("%d %d\n",minval,maxval);
}
int main(void)
{
int T;
sci(T);
for(;T--;)
{
scanf("%s",A);
n = strlen(A);
sci(m);
_for(i,0,m)
{
scanf("%s",s[i]);
Len[i] = strlen(s[i]);
}
maxval = 0;
//cerr<<A<<endl;
solve();
}
return 0;
}