Three drafts

dynamic programming diffing similarity matrix

A textbook paragraph was edited twice: first for style, then for facts. The editor wants to know what survived both edits, which words stayed in place in all three drafts. Words may be dropped from any draft, but the order of the rest may not change: you need the longest sequence of words that reads in each of the three drafts if the rest is skipped.

A word is a piece between spaces, with all its punctuation: “text,” and “text” are different words. The second example and one of the hidden tests are a real paragraph of this site’s course, in its Russian edition, in three drafts.

Input

Three lines, three drafts, from old to new. Each has from 1 to 120 words separated by single spaces.

Output

The first line holds the largest number of words k. The second, the words themselves separated by spaces (an empty line if k = 0). If there are several options, print any.

Examples

Example 1

Input

зима весна лето
лето зима весна
лето осень

Output

1
лето

Example 2

Input

4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». Через несколько дней, вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. Каждый сброс стоил части собранных данных, а повторялись сбросы снова и снова.
4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». Через несколько дней, вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. Сбросы повторялись, и каждый стоил части собранных данных.
4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». В первые же дни, вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. Сбросы повторялись, и каждый обрывал программу работ, заданную с Земли на этот день.

Output

36
4 июля 1997 года посадочный аппарат Mars Pathfinder сел в долине Арес на Марсе и выпустил на грунт маленький вездеход «Соджорнер». вскоре после того как аппарат начал собирать метеорологические данные, его компьютер стал перезагружаться целиком. и

Limits

Time · Python: 3000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The first thought: find the common part of the first two drafts, then the common part of the result and the third. Check it on the first example: winter, spring, summer.

2Hint 2

For two strings the table is two-dimensional: a cell is the pair “how many words taken from the first, how many from the second”. What should a cell remember if there are three strings?

3The idea

Two drafts can have many longest common subsequences, and the gluing “first two, then the third” takes one of them and may choose an unlucky one: in the first example “winter spring summer” and “summer winter spring” have a single common part, “winter spring”, and the third draft shares not one word with it, although “summer” is in all three. So compute for all three at once: T[i][j][k] is the length of the longest common subsequence of the first i, j and k words. If the last words of all three beginnings are equal, T = 1 + T[i − 1][j − 1][k − 1]; otherwise, the largest of the three cells where one of the beginnings is a word shorter.

4Walkthrough

The proof is the same as for two strings. Look at the last words of the three beginnings. If all three are equal, the best answer can be taken to end with this word in all three: otherwise its last word can be replaced by it. If not all are equal, at least one of the three last words does not stand at the end of the answer, and it can be thrown out: a problem with one beginning shorter remains.

The table has 121³ ≈ 1.8 million cells. In Python it is convenient to keep it as a flat list and compute the index i · S + j · W + k, where W = r + 1 and S = (q + 1)(r + 1): this is faster than a list of lists of lists. The words themselves are recovered by a path back from the far corner: if the three words are equal and the cell was obtained diagonally, the word goes into the answer and the step is diagonal; otherwise a step to the neighbouring cell with the same number.

The second example is a real paragraph about Mars Pathfinder in three drafts. Gluing two answers loses one word there: 35 instead of 36.

4+Solution

5Complexity

O(p · q · r) time and memory. For k strings the table is k-dimensional and grows as n^k; David Maier showed in 1978 that for an arbitrary number of strings the problem is NP-hard, so no fast exact algorithm is expected for many strings.

6Common mistakes

LCS(LCS(a, b), c). Fails the first example: of the many common parts of two drafts one is taken, and not necessarily the one that suits the third.
Pairwise lengths. The smallest of the three pairwise lengths is only an upper bound: the common part of all three can be shorter.
Words without punctuation. By the statement “text,” and “text” are different words; compare the pieces between spaces as they are.

Algorithms behind it

DP Algorithm Longest common subsequence The longest chain common to two sequences: an m × n table, a path back, Hirschberg. O(m · n) 2 problems