94 lines
2.4 KiB
C++
94 lines
2.4 KiB
C++
#include <cstdint>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <unordered_map>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
typedef uint64_t hash_t;
|
|
static inline hash_t Hash(char *str, int len) noexcept {
|
|
/* Reference: http://xorshift.di.unimi.it/splitmix64.c */
|
|
hash_t ret = 0;
|
|
static char inner_salt[17] = "si9aW@zl#2$3%4^!";
|
|
int i = 0;
|
|
for (; i + 8 <= len; i += 8) {
|
|
ret ^= *reinterpret_cast<const hash_t *>(str + i);
|
|
ret ^= *reinterpret_cast<const hash_t *>(inner_salt + (i & 15));
|
|
ret += 0x9e3779b97f4a7c15;
|
|
ret = (ret ^ (ret >> 30)) * 0xbf58476d1ce4e5b9;
|
|
ret = (ret ^ (ret >> 27)) * 0x94d049bb133111eb;
|
|
ret ^= ret >> 31;
|
|
}
|
|
for (; i < len; ++i) {
|
|
ret ^= str[i];
|
|
ret ^= inner_salt[i & 15];
|
|
ret += 0x9e3779b97f4a7c15;
|
|
ret = (ret ^ (ret >> 30)) * 0xbf58476d1ce4e5b9;
|
|
ret = (ret ^ (ret >> 27)) * 0x94d049bb133111eb;
|
|
ret ^= ret >> 31;
|
|
}
|
|
return ret;
|
|
}
|
|
const int kMaxN = 1005;
|
|
const int kMaxM = 1e5 + 10;
|
|
int n, m;
|
|
unordered_map<hash_t, int> wanted, cnt;
|
|
hash_t paragraph[kMaxM];
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
char tmp[15];
|
|
scanf("%d", &n);
|
|
for (int i = 0; i < n; i++) {
|
|
scanf("%s", tmp);
|
|
wanted[Hash(tmp, strlen(tmp))] = 1;
|
|
}
|
|
scanf("%d", &m);
|
|
int count_needed = 0;
|
|
for (int i = 0; i < m; i++) {
|
|
scanf("%s", tmp);
|
|
paragraph[i] = Hash(tmp, strlen(tmp));
|
|
if (wanted.find(paragraph[i]) != wanted.end() &&
|
|
wanted[paragraph[i]] == 1) {
|
|
count_needed++;
|
|
wanted[paragraph[i]] = 2;
|
|
}
|
|
}
|
|
printf("%d\n", count_needed);
|
|
int L = 0, R = -1, current_have = 0;
|
|
while (current_have < count_needed) {
|
|
R++;
|
|
if (wanted.find(paragraph[R]) != wanted.end()) {
|
|
cnt[paragraph[R]]++;
|
|
if (cnt[paragraph[R]] == 1) current_have++;
|
|
}
|
|
}
|
|
while (L <= R) {
|
|
if (wanted.find(paragraph[L]) == wanted.end()) {
|
|
L++;
|
|
} else if (cnt[paragraph[L]] >= 2) {
|
|
cnt[paragraph[L]]--;
|
|
L++;
|
|
} else
|
|
break;
|
|
}
|
|
int res = R - L + 1;
|
|
while (R + 1 < m) {
|
|
R++;
|
|
if (wanted.find(paragraph[R]) != wanted.end()) {
|
|
cnt[paragraph[R]]++;
|
|
while (L <= R) {
|
|
if (wanted.find(paragraph[L]) == wanted.end()) {
|
|
L++;
|
|
} else if (cnt[paragraph[L]] >= 2) {
|
|
cnt[paragraph[L]]--;
|
|
L++;
|
|
} else
|
|
break;
|
|
}
|
|
res = min(res, R - L + 1);
|
|
}
|
|
}
|
|
printf("%d\n", res);
|
|
return 0;
|
|
} |