0118. Coincidence

Input file name:	maxcon.im
Output file name:	maxcom.out
Time limit:	500 ms
Memory limit:	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

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version