本文共 2147 字，大约阅读时间需要 7 分钟。
有一些要的单词，然后有一个句子，问你这个句子中选一个段，使得竟可能包含更多种你要的单词，其次长度要尽可能短。
问你最多能包含的要的单词种数，和此时最短的长度。首先，我们看第一个输出怎么求。
很明晰，因为首先就是要让包含的单词种树尽可能多，那就是在句子中出现的要的单词都一定要。
那这个我们可以用 hash 把字符串转换成数字，然后通过把要的单词组成的字符串按 hash 值排序后二分，就可以得到一个单词是否是要的单词，而且还可以得出是哪个要的单词。 那第一个输出就做出来了。然后看第二个。
我们考虑用尺取法。 尺取法通常是指对数组保存一对下标(起点,终点),然后根据实际情况交替推进两个端点直到得出答案的方法,这种操作很像是尺取虫爬行的方式故得名。 其作用就是对给定的一个序列，在序列中寻找包含全部需求的，长度最小的一段子序列的O(n)的优秀算法。当然，它还有很多别的作用。#include#include #include #define ull unsigned long long#define mi 131ullusing namespace std;struct hhash { ull hash; int num;}hash[1001];int n, m, size, ans, place[100001], l, r, mid, num, in[1001], answer;char rem[1001][14], pas[100001][14];bool have[1001];ull thash;bool cmp(hhash x, hhash y) { return x.hash < y.hash;}int getplace() { //通过二分找到要背的单词种是否有这个 hash 值 l = 0; r = n; while (l <= r) { mid = (l + r) >> 1; if (hash[mid].hash > thash) { r = mid - 1; } else if (hash[mid].hash < thash) l = mid + 1; else return hash[mid].num; } return -1;}int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%s", &rem[i]); size = strlen(rem[i]); hash[i].num = i;//记录原有的位置 hash[i].hash = rem[i][0] - 'A' + 1; for (int j = 1; j < size; j++) hash[i].hash = hash[i].hash * mi + rem[i][j] - 'A' + 1;//得到hash值 } sort(hash + 1, hash + n + 1, cmp);//排序，让后面可以二分查找是否是这个字符串 scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf("%s", &pas[i]); size = strlen(pas[i]); thash = pas[i][0] - 'A' + 1; for (int j = 1; j < size; j++) thash = thash * mi + pas[i][j] - 'A' + 1; place[i] = getplace(); if (place[i] != -1 && !have[place[i]]) { ans++; have[place[i]] = 1; } } printf("%d\n", ans); if (!ans) { printf("0"); return 0; } l = 1; answer = 2147483647;//尺取法得到最小长度 for (int i = 1; i <= m; i++) { if (place[i] != -1) { if (!in[place[i]]) { num++; } in[place[i]]++; if (num == ans) { while (l <= i && num == ans) { if (place[l] != -1) { in[place[l]]--; if (!in[place[l]]) { num--; answer = min(answer, i - l + 1); } } l++; } } } } printf("%d", answer); return 0;}
转载地址：http://qpvh.baihongyu.com/