nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

题意

给你两个串s,t和一个数k,询问是否存在s的k个不重叠子串按原顺序排列后能组成 t,

数据范围

$|s|<1e5$,$|t|<1e5$,$k<100$,时间30s

题解

设状态$dp1[i][j]$代表串$s$从$s[1]$匹配到$s[i]$的时候选择了$k$个不重叠子串后,能够匹配到t串到最远位置。

设状态$dp2[i][j]$代表串s从$s[1]$匹配到$s[i]$的时候选择了$k$个不重叠子串且最后一个子串以$s[i]$结尾后,能够匹配到t串到最远位置。

根据定义$dp1[i][j]=max(dp2[t][j]), \forall t<=i$,于是简单的写出了转移式子:$dp1[i][j]=max(dp1[i-1][j],dp2[i][j])$

复杂的是$dp2[i][j]$不好得到,根据定义,$dp2[i][j]$一定会选择$s[i]$作为结尾的,现在分两类来讨论:

  1. $s[i]$单独为一个子串,那么可以由$dp1[i-1][j-1]$转移过来,

  2. $s[i]$可能不单独为一个子串,是跟前面的某串拼在一起的,那么可以由$dp2[i-1][j]$转移过来。

知道了转移来源,但是状态转移过来了,值要怎么更新呢?处理不好的话,更新是个麻烦事,这里我们预处理出$t$串里面从$t[1]$到$t[i]$中字符$ch$最后一次出现的位置,成为$max_index_before[i][ch]$

于是我们就有了转移式:

1
2
3
4
dp2[i][j]=max(
max_index_before[dp1[i-1][j-1]+1][s[i]],
max_index_before[dp2[i-1][j]+1][s[i]]
);

​ 最后处理一下边界情况,把输入进来的s变成"@&"+s,把t变成"@"+t,k增大1,边界就简单了。最终答案在$dp1[n][k]$中。

时间复杂度O(nk)

做完了之后翻了下题解,没有人用我这方法做这个题目。。。。。。

正解如下:

考虑$dp[i][j]$就是我上文所谈到的$dp1[i][j]$,他没有$dp2[i][j]$,所以不能像我那样转移了。用到了“我为人人”的转移思路,$dp[i][j]$如果转移走的时候花费一次取子串,就能够转移到$dp[i+len][j+1]$,其中len代表lcp(s.suffix(i+1),t.suffix(dp[i][j]+1)),这个地方的lcp可以用后缀数组+rmq预处理优化为O(1),如果不花费就转移到了$dp[i+1][j]$。总体上时间复杂度为O(nlogn+nk),时间复杂度较前一个做法偏高,代码也很长。

事实也是如此

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
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+555;
char s[MAXN],t[MAXN];
int dp1[MAXN][105];//前i的匹配最远
int dp2[MAXN][105];//i必须匹配的最远的
int max_index_before[MAXN][256];

int main(){
int T,n,m,k;
scanf("%d",&T);
while(T--){
//@&---
//@---
scanf("%d%d%d%s%s",&n,&m,&k,s+3,t+2);
n+=2;
m++;
k++;
s[1]=t[1]='@';
s[2]='&';

int max_index[256];
for(int i=0;i<256;i++){
max_index[i]=0;
}
for(int i=1;i<=m;i++){
max_index[t[i]]=i;
for(int j='a';j<='z';j++){
max_index_before[i][j]=max_index[j];
}
max_index_before[i]['@']=max_index['@'];
max_index_before[i]['&']=max_index['&'];
}

for(int i=1;i<=n;i++){
dp1[i][1]=1;
dp2[i][1]=0;
}
dp2[1][1]=1;

for(int j=1;j<=k;j++){
dp1[1][j]=dp2[1][j]=1;
}

for(int i=2;i<=n;i++){
for(int j=2;j<=k;j++){
dp2[i][j]=max(max_index_before[dp1[i-1][j-1]+1][s[i]],max_index_before[dp2[i-1][j]+1][s[i]]);
dp1[i][j]=max(dp1[i-1][j],dp2[i][j]);
}
}

if(dp1[n][k]==m)puts("YES");
else puts("NO");
}
}
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
113
114
#include<bits/stdc++.h>
using namespace std;

//定义以s[i]开头的后缀是suf(i)
//后缀数组性质:suf(sa[i])<suf(sa[i+1])
//模版从下标为1的地方开始,引入的字符串下标也要从下标为1开始

struct SA{
static const int MAXN=2e5+555;
static int lg[MAXN];
int h[MAXN][20],rank[MAXN],sa[MAXN],n;

void init(char*s,int len){//第一个参数要是从下标为1开始的字符串,第二个参数是要从下标为
static int x[MAXN],y[MAXN],c[MAXN];//全部是辅助数组
n=len;//初始化后缀数组内部的n->s后缀数组长度
int m=1000;//桶的大小
for(int i=1;i<=n;i++)sa[i]=y[i]=0;//初始化sa,y
for(int i=1;i<=n;i++)x[i]=s[i];//把s复制到x
for(int i=1;i<=m;i++)c[i]=0;//初始化c
for(int i=1;i<=n;i++)c[x[i]]++;//对x计数
for(int i=1;i<=m;i++)c[i]+=c[i-1];//计数前缀和
for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;//按照计数排序后的结果
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;i++)c[i]=0;//初始化c
for(int i=1;i<=n;i++)c[x[i]]++;//对x计数
for(int i=1;i<=m;i++)c[i]+=c[i-1];//计数前缀和
for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i];
for(int i=1;i<=n;i++)y[i]=x[i];
for(int i=1;i<=n;i++)x[i]=0;
num=1;
x[sa[1]]=1;
for(int i=2;i<=n;i++){
if((y[sa[i]]!=y[sa[i-1]])||(y[sa[i]+k]!=y[sa[i-1]+k])){
x[sa[i]]=++num;
}
else x[sa[i]]=num;
}
if(num>=n)break;
m=num;
}
for(int i=1;i<=n;i++)rank[i]=x[i];
//获取高度数组
int k=0;
for(int i=1;i<=n;i++){
if(k)k--;
int j=sa[rank[i]-1];
while((i+k<=n)&&(j+k<=n)&&(s[i+k]==s[j+k]))k++;
h[rank[i]][0]=k;
}
//对高度数组做rmq
for(int j=1;j<20;j++){
int d=1<<j;
for(int i=1;i+2*d-1<=n;i++)h[i][j]=min(h[i][j-1],h[i+d][j-1]);
}
if(lg[1]!=0)for(int i=1;i<MAXN;i++)lg[i]=trunc(log(i+0.5)/log(2));
}

int lcp(int x,int y){//注意没有下标检查,如果访问越界的话,会错。
int L=min(rank[x],rank[y])+1;
int R=max(rank[x],rank[y]);
int k=lg[R-L+1];
return min(h[L][k],h[R-(1<<k)+1][k]);
}
}sa;
int SA::lg[SA::MAXN];

const int MAXN=1e5+555;
char s[MAXN<<1];
int dp[MAXN][105];

int main(){
int T,n,m,k;
scanf("%d",&T);
while(T--){
//@&---
//@---
scanf("%d%d%d",&n,&m,&k);
n+=2;
m++;
k++;
char*t=s+n;

scanf("%s%s",s+3,t+2);
s[1]=t[1]='@';
s[2]='&';

sa.init(s,n+m);

for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i][j]=0;
}
}

for(int i=1;i<=n;i++)dp[i][1]=1;
for(int j=1;j<=k;j++)dp[1][j]=1;

for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);//not choose

if(dp[i][j]>=m)continue;//此处为下标检查
int len=sa.lcp(i+1,n+dp[i][j]+1);
dp[i+len][j+1]=max(dp[i][j]+len,dp[i+len][j+1]);//choose

}
}

if(dp[n][k]==m)puts("YES");
else puts("NO");
}