两个点RE,一点WA,另一个OJ全RE
#include <bits/stdc++.h>
#define int long long
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define lowbit(x) (x & -x)
using namespace std;
const int DM[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};
const int HASHMOD = 9223372036854775783;
const int HASHBASE = 131;
const int HASHITEM = 999997;
inline void read(int &res)
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
res = x * f;
}
int get_hash(string s)
{
int res = 0;
for (int i = 0; i < s.size(); i++)
{
res = (res * HASHBASE % HASHMOD + s[i] - 'a') % HASHMOD;
}
return res;
}
struct HashTable
{
struct Edge
{
int v, c;
};
vector<Edge> e[HASHITEM * 2];
void clear()
{
for (int i = 0; i < HASHITEM; i++)
{
e[i].clear();
}
}
bool find(int val)
{
int tmp = val % HASHITEM, it = 0;
for (auto en : e[tmp])
{
if (en.v == val)
{
e[tmp][it].c++;
return 1;
}
it++;
}
return 0;
}
void erase(int val, int &chan)
{
int tmp = val % HASHITEM, ite = 0;
vector<Edge>::iterator it = e[tmp].begin();
for (auto en : e[tmp])
{
if (en.v == val)
{
e[tmp][ite].c--;
if (e[tmp][ite].c == 0)
{
e[tmp].erase(it);
chan--;
}
break;
}
it++;
ite++;
}
}
void insert(int val, int &chan)
{
if (find(val))
{
return;
}
int tmp = val % HASHITEM;
e[tmp].push_back({val, 1});
chan++;
}
} ht;
int bh[1000001];
bitset<10000001> in;
signed main()
{
int n, m, ans1 = 0, ans2 = (1 << 30);
cin >> n;
string s;
for (int i = 1; i <= n; i++)
{
cin >> s;
ht.insert(get_hash(s), ans1);
}
ans1 = 0;
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> s;
bh[i] = get_hash(s);
if (ht.find(bh[i]))
{
in[i] = 1;
}
}
ht.clear();
for (int i = 1; i <= m; i++)
{
if (in[i])
{
ht.insert(bh[i], ans1);
}
}
cout << ans1 << '\n';
ht.clear();
int now = 0;
for (int l = 1, r = 0; l <= m; l++)
{
while (now < ans1 && r < m)
{
r++;
if (in[r])
{
ht.insert(bh[r], now);
}
}
if (now == ans1)
{
ans2 = min(ans2, r - l + 1);
}
if (in[l])
{
ht.erase(bh[l], now);
}
}
cout << ans2;
return 0;
}