当前位置：首页 > news >正文

最左侧冗余覆盖子串

news 2025/8/16 3:22:49

题目描述
给定两个字符串 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

"""
如果只是简单的滑动窗口的话，时间复杂度为O(n^2)
可能因为数量级高而超时，因此需要优化一下
"""
def sliding(S1,S2,K):n1 = len(S1)n2 = len(S2)if n2<n1+K:return -1#统计一下S1中每个字符出现的次数count={}for c in S1:if count.get(c) is None:count[c] = 1else:count[c]+=1#记录S1中字符的总数、total = n1windows_len = n1+KmaxI = n2-windows_len  #可以滑动的最大范围# 统计 s2 的 0 到windows范围内出现的 s1 中字符的次数for j in range(windows_len):c = S2[j]if count.get(c) is not None:if count[c]>0:total-=1    #找到了一个字符count[c]-=1if total==0:return 0  #返回起始索引# 从左边界 1 开始的滑动窗口，利用差异思想避免重复计算for i in range(1,maxI):#滑动窗口右移更新窗口remove = S2[i-1] #移除的字符add    = S2[i+windows_len-1] #加入的字符if count.get(remove) is not None:if count[remove]>=0:#如果 count[remove] 非负，说明它在有效字符之内total+=1count[remove]+=1if count.get(add) is not None:if count[add]>0:total-=1count[add]-=1if total == 0:return ireturn -1
if __name__ == '__main__':S1 = input()S2 = input()K = int(input())result = sliding(S1,S2,K)print(result)