[CF566A] Matching Names

刷一些字符串题

题意

有两组字符串,每组各n个,使组间两两匹配,求LCP长度之和最大值。

思路

我们把字符串建到Trie上。

显然对每个节点及其子树,贪心在越深处匹配越佳。

于是对Trie进行dfs()一下。

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
const int N = 800080,C = 26;
int sz = 0,ch[N][C];
int n;
char buf[N];
std::vector<int> val[N][2];
int vis[N][2];
int match[N];
void insert(char *S,int k,int id)
{
int l = strlen(S),u = 0;
val[u][k].push_back(id);
for(int i = 0,c = S[i] - 'a';i < l;c = S[++i] - 'a')
{
if(!ch[u][c])
{
sz++;
memset(ch[sz],0,sizeof(ch[sz]));
val[sz][k].clear();
ch[u][c] = sz;
}
u = ch[u][c];
val[u][k].push_back(id);
}
}
int dfs(int u,int dep)
{
int ans = 0;
for(int c = 0;c < C;c++) if(ch[u][c]) ans += dfs(ch[u][c],dep + 1);
std::vector<int> tmp[2];
for(int k = 0;k <= 1;k++) for(int j = 0,jsz = val[u][k].size();j < jsz;j++) if(!vis[val[u][k][j]][k]) tmp[k].push_back(val[u][k][j]);
int cnt = std::min(tmp[0].size(),tmp[1].size());
ans += dep * cnt;
for(int j = 0;j < cnt;j++) vis[tmp[0][j]][0] = vis[tmp[1][j]][1] = 1,match[tmp[0][j]] = tmp[1][j];
return ans;
}
int main()
{
memset(vis,0,sizeof(vis));memset(ch,0,sizeof(ch));
scanf("%d",&n);
for(int i = 1;i <= n;i++){scanf("%s",buf);insert(buf,0,i);}
for(int i = 1;i <= n;i++){scanf("%s",buf);insert(buf,1,i);}
printf("%d\n",dfs(0,0));
for(int i = 1;i <= n;i++) printf("%d %d\n",i,match[i]);
return 0;
}