CF1729G Cut Substrings
The main idea of the topic
given two non-empty strings
the s
the s
s and
t
t
t, each time the string can be
the s
the s
any string in s
t
t
t delete, find the minimum number of deletions to make the string
the s
the s
no string will appear in s
t
t
t, and find out how many different solutions there are.
If the deleted sequence is the same but in a different order, it is also considered the same scheme. like
{
3
,
5
}
\{3,5\}
{3,5} and
{
5
,
3
}
\{5,3\}
{5,3} is the same scheme.
Output the pair of the minimum number of deletions and the number of solutions deleted with the minimum number of deletions
1
0
9
+
7
10^9 + 7
109 + 7 modulo value.
have
q
q
q group data.
1
≤
q
≤
50
1\leq q\leq 50
1≤q≤50,
1
≤
∑
∣
the s
∣
≤
500
1\leq \sum|s|\leq 500
1≤∑∣s∣≤500,
1
≤
∑
∣
t
∣
≤
500
1\leq \sum|t|\leq 500
1≤∑∣t∣≤500
Problem solution
set up
the s
the s
The length of s is
no
no
n,
t
t
The length of t is
m
m
m.
ask first
t
t
t in
the s
the s
The position where it appears in s. KMP can be used, but it is not necessary. The total time complexity of violence is
o
(
∑
(
no
x
m
)
)
O(\sum(n\times m))
O(∑(n×m)), while
∑
(
no
x
m
)
≤
(
∑
no
)
x
(
∑
m
)
≤
250000
\sum(n\times m)\leq (\sum n)\times (\sum m)\leq 250000
∑(n×m)≤(∑n)×(∑m)≤250000 is completely possible.
Let each position be
a
1
,
a
2
,
…
,
a
k
a_1,a_2,\dots,a_k
a1?, a2?,…, ak?.
k
=
0
k=0
k=0 requires special judgment, output 0,1.
set up
f
i
f_i
fi? means let go
i
i
The minimum number of deletions that do not exist in i positions,
g
i
g_i
gi? represents its scheme number. The first deleted two paragraphs cannot intersect, so that
k
k
k satisfies
a
k
>
a
i
+
m
?
1
a_k>a_i + m-1
ak?>ai? + m?1 the smallest number, then transfer to
f
j
=
min
?
(
f
j
,
f
i
+
1
)
f_j=\min(f_j,f_i + 1)
fj?=min(fj?,fi? + 1), where
j
>
i
j>i
j>i and
a
j
≤
a
k
+
m
?
1
a_j\leq a_k + m-1
aj?≤ak? + m?1
Notice
i
=
1
i=1
When i=1, for satisfying
a
j
≤
a
i
+
m
?
1
a_j\leq a_i + m-1
aj?≤ai?+m?1
j
j
j,
f
j
=
1
f_j=1
fj?=1.
begging
f
f
f
g
g
g is enough, see the code for details.
The time complexity is
o
(
∑
(
no
x
m
)
+
∑
no
2
)
O(\sum(n\times m) + \sum n^2)
O(∑(n×m) + ∑n2).
code
#include <bits/stdc++.h>
using namespace std;
int T,s1,t1,a1,a[505];
long long ans1, ans2, f[505], g[505];
long long mod=1000000007;
char s[505],t[505];
void gt(){<!-- -->
for(int i=1;i<=s1-t1 + 1;i + + ){<!-- -->
int j=1;
for(j=1;j<=t1 & amp; & amp;s[i + j-1]==t[j];j ++ );
if(j==t1 + 1) a[ + + a1]=i;
}
}
int main()
{<!-- -->
scanf("%d", &T);
while(T--){<!-- -->
scanf("%s%s",s + 1,t + 1);
s1=strlen(s + 1);
t1=strlen(t + 1);
a1=0;gt();
if(a1==0){<!-- -->
printf("0 1\
");
continue;
}
for(int i=1;i<=a1;i + + ){<!-- -->
f[i]=1e9;g[i]=0;
}
for(int j=1;a[j]<=a[1] + t1-1 & amp; & amp;j<=a1;j + + ){<!-- -->
if(f[j]>1){<!-- -->
f[j]=1;
g[j]=1;
}
else if(f[j]==1){<!-- -->
g[j]=(g[j] + g[1])%mod;
}
}
for(int i=1;i<=a1;i + + ){<!-- -->
int lst=i + 1;
while(a[lst]<=a[i] + t1-1 & amp; & amp;lst<=a1) + + lst;
if(lst>a1) continue;
for(int j=lst;a[j]<=a[lst] + t1-1 & amp; & amp;j<=a1;j + + ){<!-- -->
if(f[j]>f[i] + 1){<!-- -->
f[j]=f[i] + 1;
g[j]=g[i];
}
else if(f[j]==f[i] + 1){<!-- -->
g[j]=(g[j] + g[i])%mod;
}
}
}
ans1=1e9; ans2=0;
for(int j=a1;a[j] + t1-1>=a[a1] & amp; & amp;j>=1;j--){<!-- -->
if(f[j]<ans1){<!-- -->
ans1=f[j];
ans2=g[j];
}
else if(ans1==f[j]){<!-- -->
ans2=(ans2 + g[j])%mod;
}
}
printf("%lld %lld\
",ans1,ans2);
}
return 0;
}