题解

题目解释

给定两个字符串 s1 和 s2，以及一个正整数 k。要求在字符串 s2 中找到一个长度为 len(s1) + k 的子串，使得：

1. 该子串包含 s1 中的所有字母；
2. 每个字母在子串中的出现次数不少于其在 s1 中的出现次数。

需要找出满足上述条件的最左侧的子串的起始下标，如果不存在这样的子串，则输出 -1。

题目内容

给定两个字符串 $s_1$ 和 $s_2$ 和正整数 $k$，其中 $s_1$ 长度为 $n_1$，$s_2$ 长度为 $n_2$。

在 $s_2$ 中选一个子串，若满足下面条件，则称 $s_2$ 以长度 $k$ 冗余覆盖 $s_1$

• 该子串长度为 $n_1 + k$
• 该子串中包含 $s_1$ 中全部字母
• 该子串每个字母出现次数不小于 $s_1$ 中对应的字母

给定 $s_1，s_2，k$，求最左侧的 $s_2$ 以长度 $k$ 冗余覆盖 $s_1$ 的子串的首个元素的下标，如果没有返回$-1$。

举例：

$s_1$ = "$ab$"

$s_2$ = "$aabcd$"

$k = 1$

则子串 “$aab$” 和 "$abc$" 均满足此条件，由于 "$aab$" 在 "$abc$" 的左侧，"$aab$" 的第一个元素下标为 $0$，因此输出 $0$

输入描述

输入三行，第一行为 $s_1$，第二行为 $s_2$，第三行为 $k$

• $s_1$ 和 $s_2$ 只包含小写字母

输出描述

最左侧的 $s_2$ 以长度 $k$ 冗余覆盖 $s_1$ 的子串首个元素下标，如果没有返回 $-1$。

备注

• $0 ≤ len(s_1) ≤ 1000000$
• $0 ≤ len(s_2) ≤ 20000000$
• $0 ≤ k ≤ 1000$

样例1

输入

ab
aabcd
1

输出

0

说明

子串$aab$和$abc$符合要求，由于$aab$在$abc$的左侧，因此输出$aab$的下标：$0$

样例2

输入

abc
dfs
10

输出

-1

说明

$s_2$无法覆盖$s_1$，输出 $-1$