Problem C
Structural Differences
The Association for Confounded Metadata is hiring, and you are applying. The job application is a programming task, which is described below. If you do well, you’ll be hired.
The Association is a clearinghouse for identifying and rectifying differences between documents that are structured with metadata. In this case, the metadata are HTML-like tags.
The goal is to compare two documents and explain whether they have:
-
identical metadata (i.e. sequences of tags),
-
similar metadata (the two sequences of tags are identical except for differences in case), or
-
different metadata.
For this program, do not worry about similarities or differences that occur outside the tags.
There are two types of tags – open and close – having the following formats:
-
Open: <TAGNAME[ ADDITIONAL DATA]>
-
Close: </TAGNAME>
Here, TAGNAME is a string of $1$ or more letters (a–z). The optional [ ADDITIONAL DATA] in an open tag may contain spaces, letters, quotations, and punctuation. In addition to the tag name, all additional data (including space), is considered relevant to the comparison.
Input
Input starts with a line containing an integer $1 \le n \le 100$ indicating the number of cases. Following this are $2n$ lines, each having between $1$ and $10\, 000$ characters. Each pair of lines represents two documents that should be compared. Tags have the format as described earlier; the characters < and > are only used to delimit tags. All open tags are properly closed and tags are properly nested.
Output
For each pair of documents, output the result from the comparison of the two documents. If they have identical metadata, output ‘identical’. If they differ only in their case, output ‘similar’ followed by a list of the names (lowercase) of the open tags that differ in the order they appear. Otherwise, output ‘different’.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 <html><head><title>ACM web page</title></head></html> <html><head><title>Association for Confounded Metadata</title></head></html> <htmL><head><title id="pagetitle">ACM web page</title></head></htmL> <html><HEAD><TITLE id="pagetitle">ACM web page</TITLE></HEAD></html> <html lang="en"><head><title>acm web page</title></head></html> <html><head><title>acm web page</title></head></html> |
identical similar html head title different |
