Author: loop3r
Date: 20260322
tag: 双指针
link: https://www.luogu.com.cn/problem/P1381

问题描述

灵梦有 $n$ 个单词想要背，但她想通过一篇文章中的一段来记住这些单词。

文章由 $m$ 个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。

输入格式

第 $1$ 行一个数 $n$，接下来 $n$ 行每行是一个长度不超过 $10$ 的字符串，表示一个要背的单词。

接着是一个数 $m$，然后是 $m$ 行长度不超过 $10$ 的字符串，每个表示文章中的一个单词。

输出格式

输出文件共 $2$ 行。第 $1$ 行为文章中最多包含的要背的单词数，第 $2$ 行表示在文章中包含最多要背单词的最短的连续段的长度。

分析

设 $s$ 记录文章中的单词，$w$ 记录要背的单词，$cnt$ 记录文章当前区间内目标单词出现的次数。$sum$ 记录文章种目标单词出现的总次数，$len$ 记录文章中最短的包含最多目标单词的连续段的长度。

$i$ 指针指向当前区间的左端，$j$ 指针指向当前区间的右端。

1. 如果新进来的单词 $s[j]$ 出现在 $w$ 中，则 $cnt[s[j]]++$。
2. 如果 $cnt[s[j]]$ 等于 $1$，则 $sum++$，并且更新 $len=j-i+1$。
3. 不停更新 $i$ 指针的位置，尝试缩短区间长度：

   while (i <= j) {
       // i 保持不动
       if (cnt[s[i]] == 1) break;
       // s[i] 曾出现过，去重，缩短区间长度
       if (cnt[s[i]] >= 2) {
           cnt[s[i]]--;
           i++;
       }
       // 去除非目标单词
       if (!w[s[i]]) i++;
   }

4. 更新答案：len = min(len, j - i + 1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n, m, sum, len;
string s[100010];
map<string, int> w, cnt;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        w[s] = 1;
    }
    cin >> m;

    for (int i = 1, j = 1; j <= m; j++) {
        cin >> s[j];
        if (w[s[j]]) cnt[s[j]]++;
        if (cnt[s[j]] == 1) {
            sum++;
            len = j - i + 1;
        }

        while (i <= j) {
            // i 保持不动
            if (cnt[s[i]] == 1) break;
            // s[i] 曾出现过，去重，缩短区间长度
            if (cnt[s[i]] >= 2) {
                cnt[s[i]]--;
                i++;
            }
            // 去除非目标单词
            if (!w[s[i]]) i++;
        }
        // 更新答案
        len = min(len, j - i + 1);
    }

    cout << sum << endl << len << endl;

    return 0;
}