Problem Statement
Note: This problem statement includes images that may not appear if you are using a plugin. For best results, use the Arena editor.
In order to attract users of other weblog management systems, bloggo offers tools for content migration. Not only is bloggo capable of reading some of its chief competitors' back-end formats, but it can analyze the HTML that must by definition emerge at the front end of any weblog.
An HTML document consists of tags, which are angle-bracketed strings that look like "<b>" or "</li>", as well as plaintext, which is everything else. Each opening tag, such as "<h1>", has a similar closing tag, in this case "</h1>". A substring that begins with an opening tag and ends with a similar closing tag is called a span. The type of a span is decided by its first and last tags, so a span that begins with "<h1>" and ends with "</h1>" is called an "h1" span. We say that the substring found between the first and last tags of a span is enclosed by the span. Each span of an HTML document encloses zero or more plaintext characters interspersed with zero or more further spans.
Thus, the spans of an HTML document form a nested structure that is described by a unique tag tree, each node of which is labeled with the type of its corresponding span. The outermost span of an HTML document is required to be of the "html" type, so the root of a tag tree is always labeled "html". If a span encloses further spans, then its corresponding node in the tag tree has children that describe, in order, each of the immediately enclosed spans. A span that encloses no further spans corresponds to a leaf of the tag tree. For example, consider the following document.
<html> <h1> Snapping Turtles </h1> <ul> <li> <h2> Common Snapping Turtle (<i>Chelydra serpentina</i>) </h2> <p> With its dark coloring, sinuous neck, and swift lunging motion, Chelydra serpentina is an adept hunter of nearly all creatures that live in or near water. A fully grown specimen, weighing on average 20 pounds with a 12-inch-long carapace, has no enemy but man. The long lifespan of the adult, reaching 30 years or more, compensates for the low hatchling survival rate. </p> <p> The snapping turtle rarely basks, preferring to lurk at the silty bottom or among underwater vegetation. Although reclusive in its element, when on land it ferociously confronts larger beasts that approach it, for it cannot withdraw into its undersized shell. It is a solitary creature, declining to fraternize within its species. </p> <p> Snapping turtle populations are jeopardized by trapping, habitat loss, and by automobile traffic crossing the overland routes of nesting females. </p> </li> <li> <h2> Alligator Snapping Turtle (<i>Macroclemys temminckii</i>) </h2> <p> Like the common snapping turtle, the alligator snapping turtle has a massive head and a generally saurian aspect. Whereas the common snapping turtle's talent for hibernation lets it range as far north as Canada, the alligator snapping turtle is restricted to the warm waters flowing into the Gulf of Mexico. </p> <p> With an average shell diameter of two feet and a weight of 150 pounds, this is the largest freshwater turtle in the world. Macroclemys temminckii's short neck requires that it lie in wait for prey, which it dispatches with a sudden blow of its powerful jaws. A unique feature of the alligator snapping turtle is a tubular pink appendage, growing from the dark interior of its mouth, which it wriggles in wormlike fashion to lure fish to their doom. </p> </li> </ul> </html>
This document has the following tag tree.
For the purpose of content migration, it is useful to know how the tag trees of a pair of HTML documents relate to each other. One interesting relationship is that of the intree, which is defined recursively. First of all, every tree is an intree of itself. In addition, if A is an intree of B and we remove any leaf from A to obtain a smaller tree A', then A' is also an intree of B. If A is an intree of B, then B is called an outtree of A. If A is both an intree and an outtree of B, then A and B are equivalent. If A is neither an intree nor an outtree of B, then A and B are incompatible.
Given a pair of
If the two documents are equivalent or incompatible, return the String "equivalent" or "incompatible", respectively. If docA is an intree of docB, return "intree X", where X is the number of nodes in docB that are not present in docA . If docA is an outtree of docB, return "outtree X", where X is the number of nodes in docA that are not present in docB.
Definition
- Class:
- bloggoDocStructure
- Method:
- compare
- Parameters:
- String[], String[]
- Returns:
- String
- Method signature:
- String compare(String[] docA, String[] docB)
- (be sure your method is public)
Constraints
- docA and docB each contain between 1 and 50 elements, inclusive
- each element of docA and docB is between 1 and 50 characters long, inclusive
- the only characters allowed in docA and docB are '<', '>', '/', 'a' to 'z', 'A' to 'Z', '0' to '9', the space character, ',', ';', '.', '!', '?', '-', '(', and ')'
- if the elements of docA or of docB are concatenated into a single string, the result is an HTML document as defined above
Examples
{"
Snapping Turtles
-
", "Common Snapping Turtle (Chelydra serpentina", ")
With its dark coloring, sinuous neck,", "and swift lunging motion, Chelydra serpentina is a", "n adept hunter.
The snapping turtle rarely", "basks.
Snapping turtle populations are jeo", "pardized by automobile traffic.
-
Alligator Snapping Turtle (", "Macroclemys temminckii)
Like the", " common snapping turtle, the alligator snapping ", "turtle has a massive head.
This is the lar", "gest freshwater turtle. A tubular pink append", "age grows from its mouth.
<", "/li>
{" turtles
snapping
-
common chelydra serpentina
", "hunter
(adept?)rarely basks
(hmm)", "jeopardized by traffic
",
" - often confused with...
alligator snapp", "ing turtle macroclemys temminckii
", "massive head
big!", "largest freshwater turtle. pink wormlike thing <", "/p>
Returns: "equivalent"
These two documents have the same structure as the example shown above.
-
{" turtles
snapping
-
common chelydra serpentina
", "hunter
(adept?)rarely basks
(hmm)", "jeopardized by traffic
",
" - often confused with...
alligator snapp", "ing turtle macroclemys temminckii
", "massive head
big!", "largest freshwater turtle. pink wormlike thing <", "/p>
{"
", "
Returns: "equivalent"
The docB here is a minimal document with the same structure.
-
{"
", "
{" snapping turtles
- common ",
"snapping turtle, chelydra serpentina
", "hunter
rarely basks
", "jeopardized by traffic
",
" - often confused with...
alligator snapp", "ing turtle macroclemys temminckii
", "massive head; largest freshwater turtle;", "pink wormlike appendage lures fish
", "
Returns: "outtree 4"
The tag tree for docB is the following. It is evident from comparison with the earlier illustration that docA has four nodes not present in docB.
{"
", "
{" turtles
snapping
-
common chelydra serpentina
", "hunter
rarely basks
", "almost never
", "jeopardized by traffic
",
" - often confused with...
alligator snapp", "ing turtle macroclemys temminckii
", "massive head
big!", "largest freshwater turtle.
pink", " wormlike lure in mouth
imposing", "sight on land or water
Returns: "intree 7"
We now have the following tag tree for docB. Here, docB has seven nodes not found in docA.
{"
", "
{"
", "
Returns: "incompatible"
{""}
{"
- ",
"
Returns: "intree 5"
{"
", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""}{"
", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""}Returns: "incompatible"
{"
", "
", "
- ", "
{"
Returns: "outtree 14"
{"
- ", "
- <", "h2>
", "
- <", "ul>
<", "/u>
<", "/i>
", "
- ", "
<", "html>
- ", "
- ", "
<", "/html>
- ", "
{"
<", "/ol>
- <", "/ol>
<", "/p>
- ", "
", "
<", "/h1>
", "
<", "li>
", "
", "
", "
", "
- ", "
- ", "
- ", "
", "
<", "/p>
<", "ol>
", "- ", "
{"
- <", "h1>
Returns: "intree 36"
{"
", "
<", "i>"}
Returns: "incompatible"
{"
{"
", "
<", "u>
- <", "html>
- ", "
{"
", "- <", "h2>
- <", "/b>
<", "/ul>
<", "/h1>
Returns: "intree 109"
", "
", "
- <", "/ol>
<", "/p>
", "
<", "/html>
", "
", "
<", "/ul>
", "
<", "/ul>
- <", "/ul>
", "
- ", "
{"
", "
", "
Returns: "outtree 214"
{"
{"
- "}
{"
<", "i>
<", "h1>"}
{"
"}Returns: "outtree 36"
{"
- <", "/li>
- <", "b>
- <", "/li>
- ", "
<", "h3>
Returns: "incompatible"
<", "h2>
{"
- ", "
<", "/h2>
", "
- ", "
- <", "/ol>
{"
", ""}{"
{"
- <", "/p>
", "
Returns: "intree 92"
<", "h1>
"}Returns: "incompatible"
- <", "h1>
<", "ul>
<", "/ol>
", "
<", "/h2>
{"
", "
- ", "
<", "ul>", "
", "
- <", "i>
<", "/h1>
Returns: "intree 55"
{"
", "
", "
- ", "
", "
{"
"}Returns: "outtree 45"
{"
{"
{"
", "
Returns: "incompatible"
", "
", "
", "
", "- <", "ul>
<", "ul>
", "
{"
- <", "/li>
<", "ul>
<", "u>
Returns: "outtree 168"
{"
"}{"
<", "/h2>
- ", "
<", "/h2>
- <", "/ul>
Returns: "intree 37"
{"
{"
Returns: "incompatible"
{"
- ", "
{"
- <", "ol>
- ", "
- <", "/li>
- <", "/li>
- ", "
{"
<", "/h2>
- <", "/ol>
", "
", "
- <", "/ul>
", "
", "<", "h3>- ", "
Returns: "intree 187"
", "
", "
", "
", "
<", "h2>
- <", "h2>
- <", "p>
<", "b>
<", "ul>
<", "h2>
<", "/h1>
{"
Returns: "outtree 217"
{"
", "
"}
{"
- ", "
- ", "
Returns: "incompatible"
{"
- ", "
{"
Returns: "outtree 69"
{"
<", "/h3>
<", "/h3>
{"
", "
", "
", "
<", "/h1>
<", "b>
<", "/h2>", "
<", "/html>
", "
", "
<", "/li>
", "", "
- ", "
Returns: "intree 200"
{""}
{"
", "
Returns: "intree 20"
{"
<", "/html>
<", "ul>
<", "/html>
<", "ul>
- <", "/li>
- <", "h1>
- <", "u>
<", "h1>
- <", "/ol>
", "
<", "b>
{"
", "
<", "/h3>
", "", "
<", "/h3>
<", "h2>
", "
", "
", "
- <", "ol>
- ", "
<", "/b>
<", "/h2>
- <", "h3>
Returns: "intree 87"
{"
<", "/p>
", "
", "
", "
<", "/h3>
<", "/h3>
<", "i>
", "
", "<", "/h3>
{"
", "
- "}
{"
- <", "u>
- "}
{"
{"
", "
Returns: "outtree 56"
{"
"}{"
<", "u>
- ", " ", "
- ", "
- ", "
", "
- ", "
{"
- ", "
{"
"}
Returns: "incompatible"
{"
{"
", "
<", "/h3>- ", "
", "
", "
", "
- <", "li>
Returns: "outtree 226"
", "
Returns: "incompatible"
", "
", "
", "
{"
", "
<", "/u>
", "
", "
", "
"}Returns: "intree 190"
", "
<", "/h2>
", "
", "
Returns: "intree 239"
{"
", "
- <", "html>
{"
<", "b>
<", "/h3>
Returns: "outtree 11"
{"
"}
{"
- ", "
Returns: "incompatible"
{"
<", "/i>
", "
<", "html>
", "
<", "html>", "
<", "h3><", "li>
<", "/b><", "/ol>
- <", "/ol>
{"
- <", "/html>"}
{"
{"
- ", "
- <", "i>
Returns: "intree 30"
{"
<", "h1>
{"
- <", "h2>
", "
"}Returns: "incompatible"
{"
{"
- ", "
- <", "/html>
- <", "h1>
Returns: "outtree 110"
- ", "
<", "p>
<", "p>
- <", "h2>
<", "ol>
", "
- ", "
- ", "
Returns: "intree 183"
{"
", "
<", "b>
<", "u><", "h2>
<", "/html><", "/h3>
Returns: "outtree 118"
{"
- "}
{"
- "}
Returns: "incompatible"
{"
- <", "h1>
<", "h2>", "
<", "h2>
- ", "
- <", "/i>
- ", "
- ", "
- ", "
", "
{"
<", "b>
<", "i>
", "- <", "/ol>
<", "html>
<", "i>
<", "p>
<", "i>
<", "p>
- ", "
<", "/p>
{"
<", "h1>
<", "h2>", "
<", "h2>
- ", "
<", "u>
<", "h2>
<", "h2>
", "
", "
<", "html>", "
- ", "
"}
Returns: "outtree 32"
{"
{"
", "
- <", "h1>
", "
", "
<", "/h1>
- ", "
- ", "
- ", "
", "
Returns: "intree 130"
{"
{"
"}Returns: "incompatible"
{"
<", "/h2>
", "
<", "/ul>
- ", "
- <", "/b>
- ", "
{"
<", "html>
- ", "
", "
<", "li>
- ", "
Returns: "intree 107"
{"
{"
<", "html>
{"
Returns: "outtree 2"
{"
- <", "/h2>
Returns: "incompatible"
{"
- ", "
", "
", "{"
", "
", "
"}
Returns: "outtree 77"
{ "
", "
{ " turtles
snapping
-
common chelydra serpentina
", "hunter
rarely basks
", "almost never
", "jeopardized by traffic
", " - often confused with...
alligator snapp", "ing turtle macroclemys temminckii
", "massive head
big!", "largest freshwater turtle.
pink", " wormlike lure in mouth
imposing", "sight on land or water
Returns: "intree 7"
{ "
", "
{ " snapping turtles
- common ", "snapping turtle, chelydra serpentina
", "hunter
rarely basks
", "jeopardized by traffic
", " - often confused with...
alligator snapp", "ing turtle macroclemys temminckii
", "massive head; largest freshwater turtle;", "pink wormlike appendage lures fish
", "
Returns: "outtree 4"
{ "
" }{ "
Returns: "incompatible"
{ "
" }{ "
" }Returns: "incompatible"
{ "
" }{ "
" }Returns: "outtree 1"
{ "
" }
{ "
" }Returns: "outtree 2"