# 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.

## 代码

#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;
}


418 I'm a teapot