题解
题目解释
给定两个字符串 s1 和 s2，以及一个正整数 k。要求在字符串 s2 中找到一个长度为 len(s1) + k 的子串，使得：
- 该子串包含
s1 中的所有字母；
- 每个字母在子串中的出现次数不少于其在
s1 中的出现次数。
P3078.最左侧冗余覆盖子串(100分)
题目内容
给定两个字符串 s1 和 s2 和正整数 k，其中 s1 长度为 n1，s2 长度为 n2。
在 s2 中选一个子串，若满足下面条件，则称 s2 以长度 k 冗余覆盖 s1
- 该子串长度为 n1+k
- 该子串中包含 s1 中全部字母
- 该子串每个字母出现次数不小于 s1 中对应的字母
给定 s1，s2，k，求最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素的下标，如果没有返回−1。
举例：
s1 = "ab"
s2 = "aabcd"
k=1
则子串 “aab” 和 "abc" 均满足此条件，由于 "aab" 在 "abc" 的左侧，"aab" 的第一个元素下标为 0，因此输出 0
输入描述
输入三行，第一行为 s1，第二行为 s2，第三行为 k
- s1 和 s2 只包含小写字母
输出描述
最左侧的 s2 以长度 k 冗余覆盖 s1 的子串首个元素下标，如果没有返回 −1。
备注
- 0≤len(s1)≤1000000
- 0≤len(s2)≤20000000
- 0≤k≤1000
样例1
输入
ab
aabcd
1
输出
0
说明
子串aab和abc符合要求，由于aab在abc的左侧，因此输出aab的下标：0
样例2
输入
abc
dfs
10
输出
-1
说明
s2无法覆盖s1，输出 −1
