题面:
https://vjudge.net/problem/UVA-11107
思路
这里给出一种字符串Hash+二分的做法.
对每个字符串分别进行Hash,再二分最长子串的长度\(L\).在判断\(L\)是否合法时,只需求出每个字符串中长度为\(L\)的不重复子串,再统计全部字符串中所有子串的个数.如果有子串出现次数大于等于\(\frac{n}{2}+1\),那么\(L\)合法.
实现上,使用map进行统计(\(cnt\))和判重(\(vis\)).对每个字符串\(s\),计算以\([1...|s| - L+1]\)为起点,长度为\(L\)的子串的hash值\(h_i\),去重后添加到\(cnt\)里.在添加过程中如果有\(cnt[h_i] \geq \frac{n}{2}+1\)那么\(L\)合法,同时将该段子串添加到答案中.输出时对答案去重输出即可,同时注意UVA的毒瘤格式要求=-=
这个做法时间效率很低(在不作优化的情况下跑了3.72s),但是比较好想和好写
代码
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3+10,maxs = 105;
const ull x = 13331;
int n;
ull xp[maxn],H[maxn][maxs];
string raw[maxs];
vector<string>ans;
bool check(int L){
bool ok = 0;
map<ull,int>cnt;
for(int k = 1;k <= n;k++){
map<ull,bool>vis;
for(int i = 1;i+L-1 <= raw[k].size();i++){
ull u = H[i+L-1][k] - H[i-1][k]*xp[L];
if(!vis[u]){
vis[u] = 1;
cnt[u]++;
if(cnt[u] >= n/2+1)ok = 1;
}
}
}
return ok;
}
void solve(int L){
map<ull,int>cnt;
for(int k = 1;k <= n;k++){
map<ull,bool>vis;
for(int i = 1;i+L-1 <= raw[k].size();i++){
ull u = H[i+L-1][k] - H[i-1][k]*xp[L];
if(!vis[u]){
vis[u] = 1;
cnt[u]++;
if(cnt[u] >= n/2+1){
string yay = "";
for(int j = i;j <= i+L-1;j++)yay += raw[k][j-1];
ans.push_back(yay);
}
}
}
}
return;
}
int main(){
xp[0] = 1;
for(int i = 1;i < maxn;i++)xp[i] = xp[i-1]*x;
bool wtf = 0;
while(scanf("%d",&n) == 1 and n){
if(wtf)cout << endl;
wtf = 1;
ans.clear();
for(int i = 1;i <= n;i++){
string u;
cin >> u;
raw[i] = u;
for(int j = 1;j <= u.size();j++)H[j][i] = H[j-1][i]*x + u[j-1] - 'a';
}
int L = 1,R = maxn,M,len = 0;
while(L <= R){
M = (L+R)/2;
if(check(M)){
len = M;
L = M+1;
}
else R = M-1;
}
solve(len);
sort(ans.begin(),ans.end());
if(ans.size() and len){
for(int i = 0;i < ans.size();i++)if(!i or ans[i] != ans[i-1])cout << ans[i] << endl;
}
else cout << "?\n";
}
return 0;
}
|