正文

H: Search Strategy2005-09-25 12:20:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/elva6401/5301.html

分享到:

2005' ACM/ICPC Asia Preliminary Internet Chengdu Site

H: Search Strategy

Submit your solution

Description

You must have enjoyed the convenience that web search engines brought to you, but have you ever attempted to build your own search engine? Now it's the time.

The common aim of different search engines is to make search results as close as possible to people's purpose. Hence there are lots of strategies to evaluate the authority of web pages being searched. The most widely used search engine Google uses a technology named PageRank to rank results pages by calculating the importance of sites where these pages come from. For simplicity, we use a simplified strategy similar with PageRank to organize search results.
Your partners have designed an internet crawler to collect web information for you, you are only required to rank search results of keyword in the rule below:

For a specific web page A, there may be some hyperlinks linked to other websites (html tag 'A'). If page A has a hyperlink to page B, we say page A contributes to the website of page B. Pages cannot contribute to their own websites even if it has countless hyperlinks to the pages within its website to avoid cheating.

Website domain can be in exactly one the following forms below:

  • www.XXXX.com
  • www.XXXX.net
  • www.XXXX.com.cn
  • www.XXXX.net.cn

XXXX should be replaced with domain name, which is a combination of digits and/or alphabets, e.g. www.test.com. Notice that a website can have multiple level (less than 5) of sub domains, sub domain name should also follow the rule of domain name, e.g. search.test.com, which is a second level domain of www.test.com, hyperlinks can link to URL of either domain or files in domain with HTTP protocol, e.g.: http://www.test.com and http://search.test.com/index.php, are both hyperlinks pointing to the same website. In some URLs, the protocol prefix is neglected. Of course, URLs and keywords are not case sensitive.

Now, your aim is to rank search results by their importance (the sum of other's contribution) to specific keywords. Pages with the same importance keep the order they appear in input.

Input

There is only one test case in the input, which begins with a number n, denoting number of web pages collected by crawler. Subsequently n pages are detailed; each page begins with a single line printed "URL:" and its URL, then a number w, tells how many keywords in the page. Keywords are separated by white spaces. Followed is a number r, denotes the number of hyperlinks in the page. Then hyperlinks are given, each occupies a single line. After all pages are given, there is a number k, means k keywords are to be searched, then keywords are printed separate by white spaces.

Output

For each keyword, you should first output a single line: "Search results of keyword ", followed by the keyword and a ":" (colon). Then the URLs of ranked results pages containing the keyword are outputted, each URL occupies a single line. Results of different keywords should be separated by a blank line.

Sample Input

2
URL:http://news.yahoo.com/acm
1
acm
1
http://news.acmer.com
URL:http://www.acmer.com/index.html
2
problem acm
0
1
acm

Sample Output

Search results of keyword acm:
http://www.acmer.com/index.html
http://news.yahoo.com/acm

阅读(4261) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册