Problem description
Po kursie z algorytmów tekstowych, Jasio nadal ma problem z odróżnieniem podciągu od podsłowa. W związku z tym, prowadzący postanowił przygotować dla niego specjalne zadanie. Dla danych słów A, B oraz S, Jasio ma obliczyć długość najdłuższego wspólnego podciągu słów A i B, takiego że zawiera S jako podsłowo.
W ramach przypomnienia: podciąg to słowo, powstałe poprzez usunięcie pewnych (być może żadnych) liter ze słowa, a następnie odczytanie pozostałych liter od lewej do prawej. Natomiast podsłowo to słowo, powstałe poprzez usunięcie pewnych (być może żadnych) liter z początku oraz końca słowa, a następnie odczytanie pozostałych liter od lewej do prawej. Na przykład dla słowa alekoala, jednym z jego podciągów jest eol, a jednym z jego podsłów jest lek.
Wejście
W pierwszych trzech wierszach wejścia znajdują się trzy słowa (składające się z małych liter alfabetu angielskiego) A, B oraz S.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć długość najdłuższego wspólnego podciągu słów A i B, takiego że zawiera S jako podsłowo. Jeżeli taki podciąg nie istnieje, Twój program powinien wypisać 0.
Ograniczenia
Długość każdego z napisów na wejściu nie przekracza 5000 znaków.
Przykład
| Input | Output | |
|
|