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 sub-strings 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 sub-
strings, 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.
docu#giori#nal#,#ment. Original#,#document#. ready#and#explore explore#and#ready gty#frsirheir:sig eir:sigtyfr#ssirh #
5 o#._O. 3 _ 4 g_s
Migrated from old NTUJ.
ICPC Kanpur, 2008
| No. | Testdata Range | Score |
|---|