В математике подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Например, последовательность BDF — это подпоследовательность последовательности ABCDEF. Подстрока строки — это непрерывная подпоследовательность данной строки. Например, BCD — это подстрока ABCDEF.
Вам даны две строки s1, s2 и еще одна строка под названием virus. Ваша задача — найти наидлиннейшую общую подпоследовательность s1 и s2, такую, что она не содержит подстроку virus.
Выходные данные
Выведите наидлиннейшую общую подпоследовательность s1, s2, не содержащую подстроку virus. Если имеется несколько решений, любое из них будет засчитано.
Если требуемой общей подпоследовательности нет, выведите 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ
|
ORZ
|
|
2
|
AA
A
A
|
0
|