最短覆盖子串问题解析

最短覆盖子串问题解析"/>

最短覆盖子串问题解析

问题描述：

给定两个字符串 a a a b b b, 试求字符串 a a a 的一个字串 s s s，使得 s s s 满足

1. 该串包含 b b b 中出现的所有字符
2. 满足条件1使该串长度最小

问题分析：

遍历 b b b ，储存所有出现过的字符。
用 l r 表示 s s s 在的 a a a 中的两个端点。
当 s s s 未满足条件1时 r++ , 满足条件1时 l++并记录答案。

例题

洛谷 P1638 逛画展
代码如下：

#pragma warning(disable:4996)
#include<stdio.h>
const int MAXn = 1e6 + 5;
const int MAXm = 2e3 + 5;
int n, m, master[MAXm], a[MAXn];struct ScalableInterval {int l = 1, r = 1, sum = 0;bool vis[MAXm];bool check(int i, int k) {master[i] += k;if (master[i] == 0 && vis[i]) {vis[i] = false;sum--;}else if (vis[i] == 0 && master[i]) {vis[i] = true;sum++;}//	printf("%d %d\n", i, k);if (sum == m)return true;else return false;}
}SI;
struct as {int l = 1, r = MAXn;
}ans;int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", a + i);while (SI.l <= n && SI.r <= n) {while (!SI.check(a[SI.r++], 1));while (SI.check(a[SI.l++], -1));if (SI.r > n + 1|| SI.l > n )break;if (SI.r - SI.l < ans.r - ans.l) {ans.l = SI.l;ans.r = SI.r;}}    printf("%d %d", ans.l - 1, ans.r - 1);return 0;
}