@[Usada_Pekora](/user/434929)
by 5k_sync_closer @ 2023-03-16 08:32:31
@[5k_sync_closer](/user/388651) Ofast+自然溢出+手写哈希表可过(
https://www.luogu.com.cn/record/54715798
by 唐一文 @ 2023-03-16 09:39:47
@[唐一文](/user/150843) 这么猛。/bx
by 5k_sync_closer @ 2023-03-16 09:44:25
@[唐一文](/user/150843) 改成 `unsigned int` 自然溢出了,还是过不去,所以 pbds 还有过去的可能性吗(
```cpp
//火车头发不出来
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
char s[12][100050];
int n, m, b, L, R, l[12];
unsigned H1[12][100050], P1[100050];
bool C(int k)
{
__gnu_pbds::gp_hash_table<unsigned, int> c[12];
for(int i = 1;i <= n;++i)
if(i != b) for(int j = k;j <= l[i];++j)
++c[i][H1[i][j] - H1[i][j - k] * P1[k]];
for(int j = k, q;j <= l[b];++j)
{
q = 0;
for(int i = 1;i <= n;++i) if(i != b)
q += c[i].find(H1[b][j] - H1[b][j - k] * P1[k]) != c[i].end();
if(q == n - 1) return 1;
}
return 0;
}
int main()
{
l[0] = 1e9;
for(int i = P1[0] = 1;i <= 100000;++i)
P1[i] = P1[i - 1] * 233;
while(~scanf("%s", s[++n] + 1))
{
if((l[n] = strlen(s[n] + 1)) < l[b]) b = n;for(int j = 1;j <= l[n];++j)
H1[n][j] = H1[n][j - 1] * 233 + s[n][j];
}
--n;R = l[b];while(L <= R)
{if(C(m = L + R >> 1)) L = m + 1;else R = m - 1;}
printf("%d", R);return 0;
}
```
by 5k_sync_closer @ 2023-03-16 09:48:19
@[唐一文](/user/150843) 还是说我哈希表求交的写法错了
by 5k_sync_closer @ 2023-03-16 09:48:47
@[5k_sync_closer](/user/388651) 双哈希可过。
by Usada_Pekora @ 2023-03-16 09:52:06
@[Usada_Pekora](/user/434929) 怎么过啊,我上面第一篇就是双哈希啊
by 5k_sync_closer @ 2023-03-16 09:52:53
所以哈希表求交集到底怎么写啊
by 5k_sync_closer @ 2023-03-16 09:53:10
@[5k_sync_closer](/user/388651) https://www.luogu.com.cn/record/104842198。
by Usada_Pekora @ 2023-03-16 09:53:29
@[Usada_Pekora](/user/434929) 所以一定要手写哈希表吗(加入任务计划.jpg
by 5k_sync_closer @ 2023-03-16 09:54:16