在数学中,子序列是可以通过删除某些元素而不改变剩余元素的顺序从另一个序列导出的序列。例如,序列BDF是ABCDEF的子序列。字符串的子串是字符串的连续子序列。例如,BCD 是 ABCDEF 的子串。
给定两个字符串 s1、s2 和另一个名为virus 的字符串。你的任务是找到 s1 和 s2 的最长公共子序列,使其不包含病毒子串。
输入
输入包含三个字符串,分三行:s1、s2 和病毒(1 ≤ |s1|、|s2|、|virus| ≤ 100)。每个字符串仅由大写英文字母组成。
输出
将s1和s2没有病毒的最长公共子序列作为子串输出。如果有多个答案,则其中任何一个都将被接受。
如果没有有效的公共子序列,则输出 0。
示例
输入 #1
AJKEQSLOBSROFGZ OVGURWZLWVLUXTH OZ
输出 #1
ORZ
输入 #2
AA A A
输出 #2
0