ZOJ Problem Set - 2366
The issue of this problem is to find out how far two strings over alphabet Z are, with respect to one weird definition of dissimilarity. For any two characters c1 and c2 from Z consider dissimilarity d(c1, c2) of c1 from c2 - non-negative integer number. If we take two strings a and b of equal length l, distance from a to b is
You are given two strings s and t. Consider all possible pairs of strings a and b of equal length over Z, such that s is a subsequence of a and t is a subsequence of b (string w of length n is a subsequence of a string v of length m if there exist 1 <= i1 < i2 < ... < in <= m such that w[j] = v[ij] for all 1 <= j <= n). Choose among them a' and b' such that dist(a', b') is minimal possible. Dissimilarity of s from t is defined as D(s, t) = dist(a', b').
Your task is to find the dissimilarity of s from t and to provide a' and b' such that D(s, t) = dist(a', b').
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
The first line of the input file contains Z - several different characters that form the alphabet for the strings we consider (1 <= |Z| <= 200, all characters have ASCII code greater than space). Next two lines contain s and t respectively. Length of each of the given strings does not exceed 2000. Next |Z| lines contain |Z| non-negative integer numbers each, j-th number of i-th line contains dissimilarity of i-th character from j-th.
On the first line of the output file print D(s, t). On the second and third lines of the output file print a' and b', such that D(s, t) = dist(a', b'), s is a subsequence of a' and t is a subsequence of b'. Length of each of a' and b' must not exceed 4000.
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #3