循序渐进的考虑这道题目怎么做：
考虑一种特殊情况：$T=aaa…$ ，然后只有一个串是 $abc…$ 的结构（首字母为 $a$ ，后面全都不是 $a$ ），然后其余一堆没有 $a$ 的垃圾串，那么这显然引导我们先要解决一个同余最短路的问题，即需要至少多少次数能够消掉一个长度为 $len$ 的后缀？
注意到，在这个问题中，我们并不关心字符串的内容是什么，我们只关心长度，不同的长度只有至多 $O(\sqrt{\sum |S_i|})$ 种。
设 $f_i$ 表示需要最少多少次才能让字符串恰好有 $i$ 个字符，$f_0=0$ ，这个时候发现，跑同余最短路会超时，多个 log ，怎么办呢？
如果你足够聪慧，就会发现，导致出现权值从而让我们不得不跑最短路的原因是我们直接做了取余操作，事实上，我们根本没必要一次性把取余操作做完，详细的说就是：
这样，权值就都是 $1$ 了，直接跑 $BFS$ 即可。
当然，我不够聪慧，我的解决方法是直接开值域个队列，不难证明 $f$ 的最大值不超过 $\max(S_i)+K$ 。
上述两种方法的时空复杂度都一样，单组数据下：
时间复杂度：$O(max(S_i)+K\sqrt{\sum |S_i|})$
空间复杂度：$O(\sum |S_i|+K)$
后面就简单了，考虑一个事情，假如我们现在已经填了 $T$ 的一个前缀，然后现在我们要填一个字符串，并且要删掉字符串的一个后缀，那么代价可以很方便的用 $f$ 计算。
设 $dp[i]$ 表示填下 $T$ 的长度为 $i$ 的前缀的最小操作次数。
那么 $dp[i]\to dp[j]$ 的转移就是所有前缀能对上 $T[i+1\to j]$ 的 $S$ 串的转移代价的最小值，这里有个匹配前缀的要求，显然用 Trie 就行了。
因此这道题目就做完了：先同余最短路算 $f$ ，然后建 $Trie$ ，最后 $dp$ 转移即可。
单组数据下：
时间复杂度：$O(26\sum S_i+K\sqrt{\sum |S_i|}+T^2)$
空间复杂度：$O(26\sum S_i+K+T)$
虽然有 $100$ 组数据，但是算一下发现这个复杂度已经足以通过此题。（注意 $S$ 是所有数据的长度总和不超过 $10^6$ ，不是单组数据的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e15;
const int N=1e6+5e3+105;
const int M=5e3+5;
int n,K;
string ss[N];char st[N];
bool v[N];int stk[N],top;
void add(int x){
if(!v[x])stk[++top]=x;
v[x]=1;
}
int h[N];
LL calc(int x){
int y=x%K;
if(!y)return x/K;
if(!h[K-y])return inf;
else return h[K-y]+x/K;
}
queue<int> q;
void bfs(){
h[0]=1;q.push(0);
while(!q.empty()){
int x=q.front();q.pop();
if(x>=K){
int y=x-K;
if(!h[y]){
h[y]=h[x]+1;
q.push(y);
}
}
else{
for(int i=1;i<=top;i++){
int y=x+stk[i];
if(!h[y]){
h[y]=h[x]+1;
q.push(y);
}
}
}
}
}
struct Trie{
int a[26];LL val;
int& operator[](int x){return a[x];}
}tr[N];int tcnt;
void cl(int x){
memset(tr[x].a,0,sizeof(tr[x].a));
tr[x].val=inf;
}
void init(){
int mxlen=0;
top=0;
for(int i=1;i<=n;i++){
v[ss[i].length()]=0;
mxlen=max(mxlen,(int)ss[i].length());
}
mxlen+=K;
memset(h,0,sizeof(int)*mxlen);
tcnt=0;
cl(0);
}
void add(string &s){
int len=s.length();
int now=0;
for(int i=1;i<=len;i++){
int x=s[i-1]-'a';
if(!tr[now][x]){
tr[now][x]=++tcnt;
cl(tcnt);
}
now=tr[now][x];
tr[now].val=min(tr[now].val,calc(len-i));
}
}
LL dp[M];
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++){
scanf("%s",st+1);
ss[i]=st+1;
add(ss[i].length());
}
bfs();
for(int i=1;i<=n;i++){
add(ss[i]);
}
scanf("%s",st+1);
int m=strlen(st+1);
for(int i=1;i<=m;i++)dp[i]=inf;
for(int i=0;i<m;i++){
int now=0;
for(int j=i+1;j<=m;j++){
now=tr[now][st[j]-'a'];
if(!now)break;
dp[j]=min(dp[j],dp[i]+tr[now].val+1);
}
}
assert(dp[m]<=inf);
if(dp[m]==inf)dp[m]=-1;
printf("%lld\n",dp[m]);
init();
}
return 0;
}
|
