E卷-最左侧冗余覆盖子串(100分)
最左侧冗余覆盖子串
问题描述
给定两个字符串 和 和正整数 ,其中 长度为 , 长度为 ,在 中选一个子串,满足:
- 该子串长度为
- 该子串中包含 中全部字母
- 该子串每个字母出现次数不小于 中对应的字母
我们称 以长度 冗余覆盖 ,给定 ,,,求最左侧的 以长度 冗余覆盖 的子串的首个元素的下标,如果没有返回 -1。
输入格式
输入三行:
- 第一行为字符串
- 第二行为字符串
- 第三行为整数
和 只包含小写字母。
输出格式
输出一个整数,表示最左侧的 以长度 冗余覆盖 的子串首个元素下标,如果没有返回 -1。
样例输入
ab
aabcd
1
样例输出
0
样例解释
无
数据范围
题解
这道题目本质上是一个滑动窗口问题,。解题思路如下:
- 首先,统计 中每个字符的出现次数。
- 使用滑动窗口在 上移动,窗口大小为 。
- 对于每个窗口,统计窗口内字符的出现次数。
- 比较窗口内的字符统计与 的字符统计,检查是否满足冗余覆盖的条件。
- 如果满足条件,返回窗口的起始索引;如果遍历完所有窗口都不满足,返回 -1。
关键点解释:
- 使用数组或哈希表来存储字符计数,可以快速进行比较。
- 滑动窗口技巧可以避免重复计算,提高效率。
时间复杂度分析:
- 统计 的字符次数:
- 滑动窗口遍历 :
- 每次窗口移动时的字符计数比较:(因为只有小写字母)
总体时间复杂度:
参考代码
- Python
def check_redundancy(s1_count, window_count):
"""
检查窗口是否冗余覆盖s1
"""
return all(window_count.get(c, 0) >= s1_count[c] for c in s1_count)
def find_redundant_substring(s1, s2, k):
"""
寻找s2中冗余覆盖s1的子串
"""
n1, n2 = len(s1), len(s2)
window_size = n1 + k
if window_size > n2:
return -1
# 统计s1中字符出现次数
s1_count = {}
for c in s1:
s1_count[c] = s1_count.get(c, 0) + 1
# 初始化窗口
window_count = {}
for c in s2[:window_size]:
window_count[c] = window_count.get(c, 0) + 1
# 检查第一个窗口
if check_redundancy(s1_count, window_count):
return 0
# 滑动窗口
for i in range(1, n2 - window_size + 1):
# 移除窗口左边的字符
window_count[s2[i-1]] -= 1
if window_count[s2[i-1]] == 0:
del window_count[s2[i-1]]
# 添加窗口右边的新字符
window_count[s2[i+window_size-1]] = window_count.get(s2[i+window_size-1], 0) + 1
# 检查当前窗口
if check_redundancy(s1_count, window_count):
return i
return -1
# 读取输入
s1 = input().strip()
s2 = input().strip()
k = int(input())
# 计算并输出结果
result = find_redundant_substring(s1, s2, k)
print(result)
- C
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_LEN 100001
bool check_redundancy(int s1_count[], int window_count[]) {
for (int i = 0; i < 26; i++) {
if (window_count[i] < s1_count[i]) {
return false;
}
}
return true;
}
int find_redundant_substring(char s1[], char s2[], int k) {
int n1 = strlen(s1);
int n2 = strlen(s2);
int window_size = n1 + k;
if (window_size > n2) {
return -1;
}
int s1_count[26] = {0};
int window_count[26] = {0};
// 统计s1中字符出现次数
for (int i = 0; i < n1; i++) {
s1_count[s1[i] - 'a']++;
}
// 初始化窗口
for (int i = 0; i < window_size; i++) {
window_count[s2[i] - 'a']++;
}
// 检查第一个窗口
if (check_redundancy(s1_count, window_count)) {
return 0;
}
// 滑动窗口
for (int i = 1; i <= n2 - window_size; i++) {
window_count[s2[i-1] - 'a']--;
window_count[s2[i+window_size-1] - 'a']++;
if (check_redundancy(s1_count, window_count)) {
return i;
}
}
return -1;
}
int main() {
char s1[MAX_LEN], s2[MAX_LEN];
int k;
scanf("%s", s1);
scanf("%s", s2);
scanf("%d", &k);
int result = find_redundant_substring(s1, s2, k);
printf("%d\n", result);
return 0;
}
- Javascript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let lines = [];
rl.on('line', (line) => {
lines.push(line);
if (lines.length === 3) {
const [s1, s2, k] = lines;
console.log(findRedundantSubstring(s1, s2, parseInt(k)));
rl.close();
}
});
function checkRedundancy(s1Count, windowCount) {
for (let c in s1Count) {
if ((windowCount[c] || 0) < s1Count[c]) {
return false;
}
}
return true;
}
function findRedundantSubstring(s1, s2, k) {
const n1 = s1.length;
const n2 = s2.length;
const windowSize = n1 + k;
if (windowSize > n2) {
return -1;
}
const s1Count = {};
const windowCount = {};
// 统计s1中字符出现次数
for (let c of s1) {
s1Count[c] = (s1Count[c] || 0) + 1;
}
// 初始化窗口
for (let i = 0; i < windowSize; i++) {
windowCount[s2[i]] = (windowCount[s2[i]] || 0) + 1;
}
// 检查第一个窗口
if (checkRedundancy(s1Count, windowCount)) {
return 0;
}
// 滑动窗口
for (let i = 1; i <= n2 - windowSize; i++) {
windowCount[s2[i-1]]--;
if (windowCount[s2[i-1]] === 0) {
delete windowCount[s2[i-1]];
}
windowCount[s2[i+windowSize-1]] = (windowCount[s2[i+windowSize-1]] || 0) + 1;
if (checkRedundancy(s1Count, windowCount)) {
return i;
}
}
return -1;
}
- Java
import java.util.*;
public class Main {
public static boolean checkRedundancy(Map<Character, Integer> s1Count, Map<Character, Integer> windowCount) {
for (char c : s1Count.keySet()) {
if (windowCount.getOrDefault(c, 0) < s1Count.get(c)) {
return false;
}
}
return true;
}
public static int findRedundantSubstring(String s1, String s2, int k) {
int n1 = s1.length();
int n2 = s2.length();
int windowSize = n1 + k;
if (windowSize > n2) {
return -1;
}
Map<Character, Integer> s1Count = new HashMap<>();
Map<Character, Integer> windowCount = new HashMap<>();
// 统计s1中字符出现次数
for (char c : s1.toCharArray()) {
s1Count.put(c, s1Count.getOrDefault(c, 0) + 1);
}
// 初始化窗口
for (int i = 0; i < windowSize; i++) {
char c = s2.charAt(i);
windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
}
// 检查第一个窗口
if (checkRedundancy(s1Count, windowCount)) {
return 0;
}
// 滑动窗口
for (int i = 1; i <= n2 - windowSize; i++) {
char removeChar = s2.charAt(i - 1);
char addChar = s2.charAt(i + windowSize - 1);
windowCount.put(removeChar, windowCount.get(removeChar) - 1);
if (windowCount.get(removeChar) == 0) {
windowCount.remove(removeChar);
}
windowCount.put(addChar, windowCount.getOrDefault(addChar, 0) + 1);
if (checkRedundancy(s1Count, windowCount)) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
int k = scanner.nextInt();
int result = findRedundantSubstring(s1, s2, k);
System.out.println(result);
scanner.close();
}
}
- Cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
bool checkRedundancy(const unordered_map<char, int>& s1Count, const unordered_map<char, int>& windowCount) {
for (const auto& pair : s1Count) {
if (windowCount.find(pair.first) == windowCount.end() || windowCount.at(pair.first) < pair.second) {
return false;
}
}
return true;
}
int findRedundantSubstring(const string& s1, const string& s2, int k) {
int n1 = s1.length();
int n2 = s2.length();
int windowSize = n1 + k;
if (windowSize > n2) {
return -1;
}
unordered_map<char, int> s1Count, windowCount;
// 统计s1中字符出现次数
for (char c : s1) {
s1Count[c]++;
}
// 初始化窗口
for (int i = 0; i < windowSize; i++) {
windowCount[s2[i]]++;
}
// 检查第一个窗口
if (checkRedundancy(s1Count, windowCount)) {
return 0;
}
// 滑动窗口
for (int i = 1; i <= n2 - windowSize; i++) {
windowCount[s2[i-1]]--;
if (windowCount[s2[i-1]] == 0) {
windowCount.erase(s2[i-1]);
}
windowCount[s2[i+windowSize-1]]++;
if (checkRedundancy(s1Count, windowCount)) {
return i;
}
}
return -1;
}
int main() {
string s1, s2;
int k;
// 读取输入
cin >> s1 >> s2 >> k;
// 计算并输出结果
int result = findRedundantSubstring(s1, s2, k);
cout << result << endl;
return 0;
}
#OD##OD机考#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记