建设公司网站新闻宣传管理制度,类似链家网站建设方案,做幼儿英语的教案网站,金华做网站报价题目描述 给定两个字符串 s1 和 s2 和正整数 k#xff0c;其中 s1 长度为 n1#xff0c;s2 长度为 n2。
在 s2 中选一个子串#xff0c;若满足下面条件#xff0c;则称 s2 以长度 k 冗余覆盖 s1
该子串长度为 n1 k
该子串中包含 s1 中全部字母
该子串每个字母出现次数…题目描述 给定两个字符串 s1 和 s2 和正整数 k其中 s1 长度为 n1s2 长度为 n2。
在 s2 中选一个子串若满足下面条件则称 s2 以长度 k 冗余覆盖 s1
该子串长度为 n1 k
该子串中包含 s1 中全部字母
该子串每个字母出现次数不小于 s1 中对应的字母
给定 s1s2k求最左侧的 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 n2n1K:return -1#统计一下S1中每个字符出现的次数count{}for c in S1:if count.get(c) is None:count[c] 1else:count[c]1#记录S1中字符的总数、total n1windows_len n1KmaxI 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 total0:return 0 #返回起始索引# 从左边界 1 开始的滑动窗口利用差异思想避免重复计算for i in range(1,maxI):#滑动窗口右移更新窗口remove S2[i-1] #移除的字符add S2[iwindows_len-1] #加入的字符if count.get(remove) is not None:if count[remove]0:#如果 count[remove] 非负说明它在有效字符之内total1count[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)
