题目描述

为了满足加入欧洲货币联盟的条件，政府需要从增加税收、出售股票、重新评估黄金储备等许多方案中作出选择。不同的政治家提出了不同的建议，政府希望找到双方都认可的内容。

现在，两位政治家分别输入一段建议。请从两段建议中找出一个最长的公共单词子序列，作为折中方案。

这里以完整的单词为单位，而不是以单个字符为单位。从每段建议中可以删除若干单词，但保留下来的单词顺序不能改变，也不要求相邻。两边最终保留的单词序列必须完全一致，并且单词数量尽可能多。

如果存在多个最长公共单词子序列，输出任意一个即可。

输入格式

输入包含多组数据，读到文件结束为止，不给出数据组数。

每组数据包含两段文本。每段文本可以占一行或多行，其中的单词均由小写英文字母组成，单词之间以空白字符分隔，没有标点符号。

每段文本以单独一行的 # 结束。# 只是结束标记，不属于文本，也不参与匹配。

两段文本之间至少有一个相同的单词。

输出格式

每组数据输出一行，包含两段文本的一个最长公共单词子序列。

相邻单词之间用一个空格分隔，最后一个单词后换行。如果有多种正确答案，输出其中任意一种即可。

输入样例 #1

die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#

输出样例 #1

die einkommen der abgeordneten muessen dringend verbessert werden

输入样例 #2

we like red apples
#
we like green apples
#

输出样例 #2

we like apples

样例解释 #2

依次保留 we、like、apples，可以得到长度为 3 的公共单词子序列。red 与 green 不同，不能匹配。

输入样例 #3

a b a
#
b a b
#

输出样例 #3

a b

样例解释 #3

a b 和 b a 都是长度为 2 的最长公共单词子序列，输出任意一个均可。

数据范围

每段文本包含至少 $1$ 个、至多 $99$ 个单词。

每个单词包含至少 $1$ 个、至多 $29$ 个小写英文字母。

每组的两段文本至少有一个公共单词。输入可能包含多组数据。

来源

洛谷 UVA531 · 原题