Спільний підрядок
Підпослідовність заданої послідовності — це послідовність, утворена шляхом видалення деяких елементів (можливо, жодного) з початкової послідовності. Для заданої послідовності X = < x_1, x_2, ..., x_m >, інша послідовність Z = < z_1, z_2, ..., z_k > є її підпослідовністю, якщо існує строго зростаюча послідовність індексів < i_1, i_2, ..., i_k > так, що для всіх j = 1, 2, ..., k, виконується x_i_j = z_j. Наприклад, Z = < a, b, f, c > є підпослідовністю X = < a, b, c, f, b, c > з індексами < 1, 2, 4, 6 >. Дано дві послідовності X та Y, потрібно знайти довжину найдовшої спільної підпослідовності для X та Y.
Вхідні дані
Вхідні дані подаються через стандартний ввід. Кожен набір даних складається з двох рядків, які представляють задані послідовності. Послідовності розділені довільною кількістю пробілів. Вхідні дані є коректними.
Вихідні дані
Для кожного набору даних програма повинна вивести довжину найдовшої спільної підпослідовності, починаючи з нового рядка.