Matching Names

题目描述

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the “Hobbit” movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.

There are $n$ students in a summer school. Teachers chose exactly $n$ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $b$ to a student with name $a$ as the length of the largest common prefix $a$ and $b$. We will represent such value as $LCP(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.

Find the matching between students and pseudonyms with the maximum quality.

题意概述

给定$2n$个字符串$s_i$，前$n$个为一组，后$n$个为一组。要求将它们建立匹配（不能匹配同一组的字符串），使得两两匹配的字符串的$LCP$的长度之和最大。求最大值及方案。

数据范围：$1 \le n \le 10^5, \ 1 \le \sum |s_i| \le 8 \times 10^5$。

算法分析

首先对所有串建立 Trie 树，并记录下每个节点是哪些串的前缀。

考虑贪心——在 Trie 树上 DFS（后序遍历），若在一个节点上有未匹配的不同组的串，则直接将它们匹配。这样做的正确性是显而易见的：若它们在之后匹配或与其他串匹配，则一定没有直接匹配更优。

具体实现时可以用 vector 启发式合并来维护每个节点上的值。

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int N = 800005;
int numn = 1, tot;
char s[N];
struct Trie {
  int child[26];
  std :: vector <int> rec[2];
} node[N];
std :: vector <std :: pair <int, int> > ans;

void insert(char s[], int id, int val) {
  int len = strlen(s), root = 0;
  for (int i = 0; i < len; ++ i) {
    if (! node[root].child[s[i] - 'a']) node[root].child[s[i] - 'a'] = numn ++;
    root = node[root].child[s[i] - 'a'];
  }
  node[root].rec[val].push_back(id);
}

void merge(std :: vector <int> &a, std :: vector <int> &b) {
  if (a.size() < b.size()) swap(a, b);
  a.insert(a.end(), b.begin(), b.end());
}

void dfs(int t, int dep) {
  for (int i = 0; i < 26; ++ i)
    if (node[t].child[i]) {
      dfs(node[t].child[i], dep + 1);
      merge(node[t].rec[0], node[node[t].child[i]].rec[0]);
      merge(node[t].rec[1], node[node[t].child[i]].rec[1]);
    }
  while (! node[t].rec[0].empty() && ! node[t].rec[1].empty()) {
    tot += dep;
    ans.push_back(std :: make_pair(node[t].rec[0][node[t].rec[0].size() - 1], node[t].rec[1][node[t].rec[1].size() - 1]));
    node[t].rec[0].pop_back(), node[t].rec[1].pop_back();
  }
}

int main() {
  int n; scanf("%d", &n);
  for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 0);
  for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 1);
  dfs(0, 0);
  printf("%d\n", tot);
  for (int i = 0; i < n; ++ i) printf("%d %d\n", ans[i].first, ans[i].second);
  return 0;
}