题目情境#
题目链接：https://www.luogu.com.cn/problem/P1381 ↗
题目描述
灵梦有 个单词想要背，但她想通过一篇文章中的一段来记住这些单词。
文章由 个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。
每个单词仅包含小写字母。
输入格式
第 行一个数 ，接下来 行每行是一个长度不超过 的字符串，表示一个要背的单词。
接着是一个数 ，然后是 行长度不超过 的字符串，每个表示文章中的一个单词。
输出格式
输出文件共 行。第 行为文章中最多包含的要背的单词数，第 行表示在文章中包含最多要背单词的最短的连续段的长度。
输入输出样例
输入 #1
3
hot
dog
milk
5
hot
dog
dog
milk
hot
输出 #1
3
3
说明/提示
- 对于 的数据，，；
- 对于 的数据，，；
- 对于 的数据，，。
算法解析#
本题使用双指针滑动窗口维护当前文章段的左右端点 和 ，并统计当前窗口内目标单词的出现次数。
- 使用
word集合标记要背的单词； - 使用
cnt记录当前区间内每个目标单词的出现次数； sum表示当前窗口内不同目标单词的个数；len记录在目标单词数量最大时的最短窗口长度。
当新的单词 进入窗口时：
- 如果它是目标单词，则
cnt[s[j]]++；若cnt[s[j]]==1，说明当前窗口新增了一个不同目标单词； - 在窗口右扩后，尝试收缩左端点 ：
- 若 是非目标单词，则直接移动 ；
- 若 是目标单词且
cnt[s[i]]>=2，则可以将其出现次数减一并移动 ； - 若
cnt[s[i]]==1，则不能再收缩，否则会丢失一个目标单词；
- 每次收缩后，用当前窗口长度更新最短长度
len。
这样可以在保证目标单词数量不减少的前提下，使窗口尽可能短。整个过程中，左右指针均最多移动 次，时间复杂度为 。
Python代码实现#
# P1381 单词背诵
# 24年新星赛-小猪的纸花
from collections import defaultdict
n = int(input())
word = defaultdict(bool)
cnt = defaultdict(int)
len = 0
sum = 0
for i in range(n):
s1 = input()
word[s1] = True
m = int(input())
s = [0] * (m + 1)
i = 1
for j in range(1, m + 1):
s[j] = input()
if word[s[j]]:
cnt[s[j]] += 1
if cnt[s[j]] == 1:
sum += 1
len = j - i + 1
while i <= j:
if cnt[s[i]] == 1:
break
if cnt[s[i]] >= 2:
cnt[s[i]] -= 1
i += 1
if not word[s[i]]:
i += 1
len = min(len, j - i + 1)
print(sum)
print(len)C++代码实现#
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s[100005],s1;
map<string,bool> word;
map<string,int> cnt;
int sum,len;
//s[] 记录文章中的单词
//word[] 记录单词表中的单词
//cnt[] 记录文章当前区间内单词出现次数
//sum 记录文章中出现单词表的单词数
//len 记录包含表中单词最多的区间的最短长度
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>s1,word[s1]=1;
cin>>m;
for(int j=1,i=1; j<=m; j++){ //i<=j
cin>>s[j];
if(word[s[j]]) cnt[s[j]]++;
if(cnt[s[j]]==1) sum++, len=j-i+1;
while(i<=j){
if(cnt[s[i]]==1) break; //保持i指针位置不动
if(cnt[s[i]]>=2) cnt[s[i]]--,i++; //去重,更优
if(!word[s[i]]) i++; //去掉非目标单词,更优
}
len=min(len,j-i+1); //更新
}
cout<<sum<<endl<<len<<endl;
}