A9873. 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 . 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.
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 . 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.
输入格式
The first line contains number $n$ ( $1<=n<=100000$ ) — the number of students in the summer school.
Next $n$ lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.
The last $n$ lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.
The total length of all the names and pseudonyms doesn't exceed $800000$ characters.
Next $n$ lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.
The last $n$ lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.
The total length of all the names and pseudonyms doesn't exceed $800000$ characters.
输出格式
In the first line print the maximum possible quality of matching pseudonyms to students.
In the next $n$ lines describe the optimal matching. Each line must have the form $a$ $b$ ( $1<=a,b<=n$ ), that means that the student who was number $a$ in the input, must match to the pseudonym number $b$ in the input.
The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.
In the next $n$ lines describe the optimal matching. Each line must have the form $a$ $b$ ( $1<=a,b<=n$ ), that means that the student who was number $a$ in the input, must match to the pseudonym number $b$ in the input.
The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.
输入输出样例
输入 #1
5 gennady galya boris bill toshik bilbo torin gendalf smaug galadriel
输出 #1
11 4 1 2 5 1 3 5 2 3 4
说明/提示
The first test from the statement the match looks as follows:
- bill $→$ bilbo (lcp = 3)
- galya $→$ galadriel (lcp = 3)
- gennady $→$ gendalf (lcp = 3)
- toshik $→$ torin (lcp = 2)
- boris $→$ smaug (lcp = 0)
- bill $→$ bilbo (lcp = 3)
- galya $→$ galadriel (lcp = 3)
- gennady $→$ gendalf (lcp = 3)
- toshik $→$ torin (lcp = 2)
- boris $→$ smaug (lcp = 0)