0118. Coincidence

Имя входного файла:	maxcon.im
Имя выходного файла:	maxcom.out
Ограничение по времени:	500 ms
Ограничение по памяти:	64 megabytes

Common subsequence of two strings s₁ and s₂ is a pair of sequences of indices ({a_i},{b_i}) such that a₁ < a₂ < …< a_k, b₁ < b₂ < …< b_k, and s₁[a_i]=s₂[b_i] for all 1 ≤ i ≤ k.

Find a longest common subsequence of two strings.

Input file

First and second line of an input file contain two strings of French lowercase characters a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.

Output file

In the first line of output file output k – the length of a longest common subsequence. On the second line output k numbers – indices of a common subsequence in the first input string. On the third line output the same for the second input string. Index of the first character in the string is 1. Indices should be output in ascending order.

Examples:

maxcon.im	maxcom.out
abcd cxbydz	2 3 4 1 5

Источник: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати