题目解析和算法源码

华为OD机试 - 最左侧冗余覆盖子串（Java & JS & Python & C & C++）_伏城之外的博客-CSDN博客

题目描述

给定两个字符串 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