第一问（哈希）

要使得包含单词最多，那么就需将文章中所有在单词表中出现过的单词全部统计。

而一个字符一个字符的比对复杂度过高，因此我们需要求出单词表与文章的字符串哈希，这样我们就可以$O(1)$比较了。而哈希之后的值是一个整数，那么我们目前的问题就转化为有两个数组$A[]$和$B[]$，$A[]$数组中有多少个不同的数在$B[]$中出现过。那么对于这个问题很显然我们可以建立一个$bool$数组$C[]$与$bool$数组$used[]$,扫 一遍$A[]$，以$A[]$中的每个元素为下标，赋值为$true$。扫一遍$B[]$，如果$C[B[i]]==true$且$used[B[i]]=false$那么$cnt++$，$used[B[i]]$赋值为$true$。

那么很显然我们就可以用哈希值作为$C[]$数组的下标（要保证在求哈希之模的数能作为数组下标）愉快的解决第一个问。

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s;
        have[hsh(s)] = true;
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> s;
        val[i] = hsh(s);
        if (have[val[i]] && !used[val[i]]){
            cnt++;
            used[val[i]] = true;
        }
    }

此步复杂度为$O(m)$

第二问

第二问暴力部分分

$O(m^3)$暴力枚举

我们可以枚举长度$len$并分别判断从第$i$个单词开始为第一个单词的长度为$len$子串是否合法（即在$B[]$中存在连续的长度为$k$的一段，包含$cnt$个单词）。其中$1≤len≤m$，判断的复杂度为$O(m^2)$

因此总复杂度为$O(m^3)$

$O(m^2\ log\ m)$暴力二分

在上面所描述的暴力中，我们将第二问转化为了一个判定问题。

而在我们所枚举的集合很显然是具有单调性的：

如果答案为$k$

那么如果长度大于$k$必然合法

而长度要是小于$k$则必然不合法

因此我们可以二分长度$len$，$check$的复杂度为$O(m^2)$，二分的复杂度为$O(log\ m)$因此总复杂度为$O(m^2\ log\ m)$。

$O(m)$正解

设$f_{l,r}$为从$B[l]$到$B[r]$这段区间内，包含$A[]$中的数的个数。

当$f_{l,r}=cnt$且$C[B[r]]=true$并满足于$C[B[r+1]]=false$时

设其中包含$cnt$个$A[]$中元素个数的最短区间为$[a,b]$（等价于$[a,r]$）

那么显然$f_{a,b}=f_{l,r}=f_{a,r}$

那么我们则可以用$r - a + 1$更新元素

我们维护一个集合$S$与$S’$，$S$包括$B[l] \sim B[r]$，$S’$包括$B[a] \sim B[r]$

那么$(r-l+1)=|S|$，$(r-a+1)=|S’|$

我们已知$l,r$与集合$S$，接下来即求出$a$与$S’$

因为$f_{l,r}=f_{a,r}=cnt$且$[a,r]$为包含$cnt$个$A[]$中元素个数的最短区间

那么$f_{a+1,r}$必然小于$cnt$

且$f_{l,r-1}$必然小于$cnt$

且$[a,r]$为连续的一段

因此我们得到$S’$最朴素的做法即从$l$开始依次删除$B[i]$所对应的集合的元素。对应的区间为$[c,r]$当$f_{c,r}<cnt$时$r-c+2$即为$r - a + 1$。

因此我们可以枚举$r$，计算$f_{1,r}$并维护集合$S$，每次枚举插入$B[r]$。

当$f_{1,r}=cnt$时依次删除前$i$个元素，直到$f_{1,r}<cnt$

并用$|S’|+1$更新答案。

而对于集合$S$，因为我们只在一端插入，一端删除，因此可以用队列维护。

而对于每个元素最多进队$1$次出队$1$次。

因此复杂度为$O(m)$。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int mod = 1000007;
const int base = 131;
bool have[mod], used[mod];
int val[100005],sum[mod];
char s[15];
queue<int> q;

int hsh(char* s){
    int ret = 0, len = strlen(s);
    for (int i = 0; i < len; i++){
        ret = (ret * base + s[i]) % mod;
    }
    return ret;
}

int main() {
    int n, m, cnt = 0, len, now;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s;
        have[hsh(s)] = true;
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> s;
        val[i] = hsh(s);
        if (have[val[i]] && !used[val[i]]){
            cnt++;
            used[val[i]] = true;
        }
    }
    if (cnt == 0){
        cout << 0 << endl;
        cout << 0 << endl;
    }else{
        len = m;
        now = 0;
        for (int i = 1; i <= m; i++){
            int queuelen = q.size();
            q.push(i);
            sum[val[i]]++;
            if (have[val[i]] && sum[val[i]] == 1) now++;
            if (now == cnt){
                while (now == cnt){
                    int v = q.front();
                    q.pop();
                    sum[val[v]]--;
                    if (sum[val[v]] == 0 && have[val[v]]) now--;
                }
                queuelen = q.size() + 1;
                len = min(len,queuelen);
            } 
        }
        cout << cnt << endl << len;
    }
    return 0;
}