2414: Information Extraction
题目描述
Extracting the information from HTML document is a complex task. For example, journalists often need to extract some news from Web site (including the title, content, time, etc.), and then made it into a specific format. Because different HTML document has different structure and the artificial way to copy and paste is too tedious, now you need to write a program to store a specific output format, the structure of some HTML documents and the mapping from the structure to the output format. When it inputs a HTML document, according to the mapping, you need to output specific format text.
HTML documents are defined as follows：
HTML
HTML stands for HyperText Markup Language.
HTML is a markup language.
A markup language is a set of markup tags.
The tags describe document content.
HTML documents consist of tags and texts.
Tags
HTML is using tags for its syntax.
A tag is composed with special characters: ‘<’, ‘>’ and ‘/’.
Tags usually come in pairs, the opening tag and the closing tag.
The opening tag starts with “<” and the tagname. It usually ends with a “>”.
The closing tag starts with “</” and the same tagname as the corresponding opening tag. It ends with a “>”.
There will not be any other angle brackets in the documents.
Tagnames are strings containing only lowercase letters.
Tags will contain no line break (‘\n’).
Except tags, anything occured in the document is considered as text content.
The length of tagname less than or equal 30
Elements
An element is everything from an opening tag to the matching closing tag (including the two tags).
The element content is everything between the opening and the closing tag.
Some elements may have no content. They’re called empty elements, like <hr></hr>.
Empty elements can be closed in the opening tag, ending with a “/>” instead of “>”.
All elements are closed either with a closing tag or in the opening tag.
Elements can have attributes.
Elements can be nested (can contain other elements).
The <html> element is the container for all other elements, it will not have any attributes.
Attributes
Attributes provide additional information about an element.
Attributes are always specified in the opening tag after the tagname.
Tag name and attributes are separated by single space.
An element may have several attributes.
Attributes come in name="value" pairs like class="icpc".
There will not be any space around the '='.
All attribute names are in lowercase.
The value of the id attribute is unique and the length less than or equal 30.
A Simple Example
<html><body>
<h3 id="header" class="style1">this is a test</h3>
<div id="content" class="style2">
this is content<br/>
<pre>var x = 1111; </pre>
</div>
</body></html>
The structure of a HTML document is the HTML document, but only have id attribute and elements have no text content. A HTML document may have many structures, because the content of some elements may be removed.
A Simple Example
<html><body>
<h3 id="header"></h3>
<div id="content"></div>
</body></html>
The specific output format like a HTML document, but the container for all other elements is not necessarily the <html> element.
A Simple Example
<news>
<title></title>
<content></content>
<flag> others </flag>
</news>
The mapping from the structure to the output format is defined as follows：
The value of a id attribute of a structure-A tagname of the ouput format
(It means the content of the element which the id belongs to should as the content of elements whose tagname is the tagname)
Two Simple Examples
header-title
content-content
输入
The first line of the input is an integer T (T<=15) representing the number of test cases.
Each test case is a specific output format (Length less than or equal 10000) in front.
Then input is an integer N (0<=N<=30) representing the number of the type of HTML document.
Each type is the structure of HTML document in front.
Then input is an integer M (0<=M<=30) representing the number of the mapping from the structure to the specific output format. Each of the next M lines is a mapping.
Each test case is a HTML document (Length less than or equal 10000) at the end.
输出
For each test case, first output a line “Case #x:”, where x is the case number (starting from 1). If there exists the structure of the HTML doument, output specific format text, otherwise output “Can't Identify”. If there exists more than one structure of the HTML doument, use the early input structure.
样例输入 复制
2
<news>
<title>default title</title>
<content width=”1000px”></content>
</news>
1
<html><h3 id="header"></h3>
<div id="content"></div></html>
2
header-title
content-content
<html><h3 id="header" class="style1">
this is a test</h3>
<div id="content" class="style2">
this is content<br/>
<pre>var x = 1111;</pre>
</div>
</html>
<xxx>
<title>default title</title>
</xxx>
1
<html><h3 id="header"></h3></html>
1
header-title
<html><h3 id="tmp">xxxx</h3></html>样例输出 复制
Case #1:
<news>
<title>
this is a test</title>
<content width=”1000px”>
this is content<br/>
<pre>var x = 1111;</pre>
</content>
</news>
Case #2:
Can't Identify