P1381 单词背诵【双指针】

P1381 单词背诵【双指针】
题目描述
灵梦有 n 个单词想要背，但她想通过一篇文章中的一段来记住这些单词。
文章由 m 个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。
输入格式
第 1 行一个数 n，接下来 n 行每行是一个长度不超过 10 的字符串，表示一个要背的单词。
接着是一个数 m，然后是 m 行长度不超过 10 的字符串，每个表示文章中的一个单词。
输出格式
输出文件共 2 行。第 1 行为文章中最多包含的要背的单词数，第 2 行表示在文章中包含最多要背单词的最短的连续段的长度。
输入输出样例
输入 #1
3
hot
dog
milk
5
hot
dog
dog
milk
hot
输出 #1
3
3
输入 #2
3
hot
dog
milk
6
hot
car
dog
milk
hot
car
输出 #2
3
3
说明/提示
数据规模与约定
对于 30% 的数据，n≤50，m≤500；
对于 60% 的数据，n≤300，m≤5000；
对于 100% 的数据，n≤1000，m≤10^5 。

以下使用双指针（尺取法）的解题思路:
变量及数组功能：

1. s[]记录文章中的单词
2. word[]记录单词表中的单词
3. cnt[]记录文章当前区间内目标单词的出现次数sum 记录文章中出现的目标单词个数
4. len 记录包含目标单词最多的区间的最短长度

算法操作过程：
i指针指向当前区间的左端，j指针指向当前区间的右端。
1.如果新来的单词 s[j]是目标单词，cnt[s[i]]++；
2.if（cnt[s[j]]==1）sum++，len=j-i+1；
3.while（i<=j）：
        if（cnt[s[i]]==1）break；//保持i指针位置不动
        if（cnt[s[i]]>=2）cnt[s[i]]--，i++；//去重，更优
        if（！word[s[i]]）i++；//去掉非目标单词，更优
4.更新最短长度 len；

#include 
using namespace std;
const int N=1e5;
int n,m,len,sum;
string s[N+5],ss;
mapbool> word;
mapint> cnt;
int main()
{	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ss;word[ss]=1;
	}
	cin>>m;
	for(int i=1,j=1;j<=m;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;
			if(cnt[s[i]]>=2){
				cnt[s[i]]--;i++;
			}
			if(!word[s[i]])i++;
		}
		len=min(len,j-i+1);
	}
	cout<
	cout<
	return 0;
}