思路讲解
子串哈希值的计算见下
P10469 后缀数组(如何算子串哈希值)
二分+哈希，其实不用先生成后缀数组，可以直接用哈希+二分算
参考以下题解
https://luogu.com.cn/article/g6xhm285
AC代码
AC
https://www.luogu.com.cn/record/198696498
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=2010,base=131;
ll N,hashe[15][MAXN],len[15],powBase[MAXN];
inline bool check(ll x){
if(x==0)
return true;
map<ll,ll> hashCnt;
for(int i=1;i<=N;++i){
unordered_set<ll> isAdd;
for(int j=0;j<=len[i]-x;++j){
ll subStringHash=hashe[i][j+x-1]-(j>0?hashe[i][j-1]*powBase[x]:0);
if(hashCnt.find(subStringHash)==hashCnt.end()){
hashCnt[subStringHash]=1;
isAdd.insert(subStringHash);
}else if(isAdd.find(subStringHash)==isAdd.end()){
hashCnt[subStringHash]+=1;
isAdd.insert(subStringHash);
}
}
}
for(map<ll,ll>::iterator it=hashCnt.begin();it!=hashCnt.end();it++){
ll val=it->second;
if(val>=N)
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N;
powBase[0]=1;
for(int i=1;i<=MAXN;++i){
powBase[i]=powBase[i-1]*base;
}
ll r=999999;
for(int i=1;i<=N;++i){
string s;
cin>>s;
len[i]=s.size();
r=min(len[i],r);
hashe[i][0]=0;
for(int j=0;j<len[i];++j){
hashe[i][j]=hashe[i][(j>0?j-1:0)]*base+s[j];
}
}
ll l=0;
while (l<r) {
ll mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<l<<'\n';
return 0;
}
|
心路历程（WA，TLE，MLE……）
WA
https://www.luogu.com.cn/record/198689007
在查哪里出问题了
搞半天原来是这里忘记insert进isAdd了。
