Problem E: Editing
Input File: E.in
Editing of original version of a document produces the final version after certain
corrections, insertions, deletions and/or reorganization of text. The original as well as the final
version of the document may be considered as a string of only case-sensitive letters, digits,
space and standard punctuation symbols: comma, full stop, semicolon and colon. In order to
avoid confusion the character # is used to represent a space character in a string. Often the
two versions contain common sub-strings of characters intermixed with uncommon substrings
scattered throughout the document.
A publishing house wants to have a computer program that will identify the difference
between the two versions of a document, given the two versions as input. You are required to
write a program for the publishing house.
The difference between the two versions is considered to be a single string containing
reduced forms of original and edited versions, separated by the underscore (_) character. The
reduced forms of two versions are obtained by deleting successively the longest common
sub-strings of length two or more from the two versions simultaneously until no more common
sub-strings exist in the two versions. In case there exist two or more longest common substrings,
the rightmost longest sub-string in the original version is selected first for deletion. If
the selected sub-string in the original version occurs more than once in the edited version
then the right most sub-string is selected for deletion.
Input may contain multiple test cases.
Each test case contains two lines. The first line contains the original version while the
second line contains the edited version of the document. Assume that each version contains
not more than 250 characters.
Input terminates with a line containing # as the first input for a test case.
For each test case, print output in one line. The line contains two fields separated by a
space. The first field is an integer representing the total number of common sub-strings
deleted; the second field is the string representing the difference between the two versions.
Can any 1 daring out here 2 take challenge of solving this big problem within 7 days