#P9661. 切割字符串

    ID: 6272 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-逆向思考支配关系区间 DP最长公共前缀滚动数组前后缀最值

切割字符串

题目描述

Alex_Wei(以下简称小 A)有一个字符串 ss。他觉得 ss 太冗长了,很不优美,于是想把它变成字符串 tt。

具体地,他可以每次砍掉 ss 的一个前缀或后缀 s′s',但必须保证 s′s' 是切割后 ss 的子串。小 A 想请你帮他 求出最少操作次数,若无解输出 −1-1。

输入格式

两行字符串,分别表示 ss 和 tt。

输出格式

一行一个整数,表示答案。

样例

abbabb
ba
3

abbabb→\toabba→\tobba→\toba。方案不唯一。

fxofoxxooffoxooo
fox
8

fxofoxxooffoxooo→\toxofoxxooffoxooo→\tofoxxooffoxooo→\toxooffoxooo→\toffoxooo→\toffoxoo→\toffoxo→\toffox→\tofox。方案可能不唯一。

tzcakioi
ycxakioi
-1
abc
ac
-1
见附加文件 cutstring5.in
见附加文件 cutstring5.ans

该样例满足 Subtask 3 的限制。

见附加文件 cutstring6.in
见附加文件 cutstring6.ans

该样例满足 Subtask 5 的限制。

数据范围

对于 100%100\% 的数据,1≤∣t∣≤∣s∣≤5×1031\le |t|\le |s|\le 5\times 10^3,字符集 ∈[a,z]\in[a,z]。

Subtask 编号 分数 特殊限制
11 11
s=ts=t
22 99 tt 仅包含 a
33 2020 ∣s∣≤100|s|\le100
44 ∣s∣≤500|s|\le 500
55 1515 ∣s∣≤1.5×103|s|\le 1.5\times 10^3
66 ∣t∣=4|t|=4,s,ts,t 字符均随机,字符集 ∈[a,c]\in[a,c]
77 2020 无特殊性质