CSI4144-19s week 06 (midterm)


2019-02-20 17:15 UTC

CSI4144-19s week 06 (midterm)


2019-02-27 17:15 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -18040 days 3:35:44

Time elapsed


Time remaining


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:


  • 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 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.


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
<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>
similar html head title