QOJ.ac

QOJ

时间限制: 1 s 内存限制: 64 MB 总分: 100

#2045. 病态路径

统计

Pathfinder 教授是万维网超链接结构方面的权威。为了建立他的假设,他一直在开发能够自动遍历超链接并分析 Web 结构的软件代理。今天,他产生了一个关于改进其软件代理的有趣想法。然而,他非常忙碌,需要优秀程序员的帮助。现在邀请你加入他的开发团队,为他的新型软件代理创建一个小巧但关键的软件模块。

在遍历超链接时,Pathfinder 的软件代理会增量生成已访问 Web 部分的地图。因此,代理需要维护已遍历超链接和已访问网页的列表。跟踪此类信息的一个问题是,两个或多个不同的 URL 可能指向同一个网页。例如,通过输入以下五个 URL 中的任何一个,你最喜欢的浏览器很可能会带你进入同一个网页,即你可能已经访问过的 ACM ICPC Ehime 大赛主页。

http://www.ehime-u.ac.jp/ICPC/ http://www.ehime-u.ac.jp/ICPC http://www.ehime-u.ac.jp/ICPC/../ICPC/ http://www.ehime-u.ac.jp/ICPC/./ http://www.ehime-u.ac.jp/ICPC/index.html

你的程序应该为 Pathfinder 的实验揭示此类别名。

好吧……但这确实是一个真正的挑战,为了做到完美,你可能需要在程序中嵌入相当复杂的逻辑。我们担心即使像你们这样优秀的程序员也无法在五小时内完成它。因此,我们将问题简化了一些,并使其稍微有些不切实际。你应该专注于 URL 的路径部分(即上述示例中的 /ICPC/、/ICPC、/ICPC/../ICPC/、/ICPC/./ 和 /ICPC/index.html),并忽略方案部分(例如 http://)、服务器部分(例如 www.ehime-u.ac.jp)以及其他可选部分。你应该仔细阅读后续描述的规则,因为其中一些可能并非基于当今 Web 和 URL 的实际情况。

本问题中的每个路径部分都是一个绝对路径名,它指定了从根目录到分层(树状)目录结构中某个网页的路径。路径名总是以斜杠(/)开头,表示根目录,后跟由斜杠分隔的路径段。例如,/ICPC/index.html 是一个包含两个路径段 ICPC 和 index.html 的路径名。

除最后一个路径段外,所有路径段都应为目录名,最后一个应为存储网页的普通文件名。但是,我们有一个例外规则:路径名末尾的普通文件名 index.html 可以省略。例如,如果 index.html 是一个现有的普通文件名,则路径名 /ICPC/index.html 可以缩写为 /ICPC/。更准确地说,如果 ICPC 是根目录下现有目录的名称,且 index.html 是 /ICPC 目录下现有普通文件的名称,则 /ICPC/index.html 和 /ICPC/ 指向同一个网页。此外,最后一个路径段后的最后一个斜杠也可以省略。也就是说,例如,/ICPC/ 可以进一步缩写为 /ICPC。但是,/index.html 只能缩写为 /(单个斜杠)。

你应该特别注意由单个句点(.)或双句点(..)组成的路径段,它们始终被视为目录名。前者表示目录本身,后者表示其父目录。因此,如果 /ICPC/ 指向某个网页,则 /ICPC/./ 和 /ICPC/../ICPC/ 都指向同一个页面。同样,如果 ICPC2 是根目录下现有目录的名称,则 /ICPC2/../ICPC/ 也指向同一个页面;否则它不指向任何网页。注意,根目录没有任何父目录,因此诸如 /../ 和 /ICPC/../../index.html 之类的路径名无法指向任何网页。

你在这项工作中的任务是编写一个程序,检查给定的两个路径名是否指向现有的网页,如果是,则检查它们是否相同。

输入格式

输入包含多个数据集。每个数据集的第一行包含两个正整数 $N$ 和 $M$,两者均小于或等于 100,并由单个空格字符分隔。

数据集的其余部分包含 $N + 2M$ 行,每行包含一个长度最多为 100 个字符的语法正确的路径名。你可以假设每个由两个斜杠包围的路径段长度至少为 1。换句话说,任何路径名中都不会出现两个连续的斜杠。每个路径段不包含字母数字字符(即 ‘a’–‘z’、‘A’–‘Z’ 和 ‘0’–‘9’)和句点(‘.’)以外的任何内容。

前 $N$ 个路径名枚举了所有网页(普通文件)。每个现有的目录名在这些路径名中至少出现一次。你可以假设这些路径名不包含仅由单个或双个句点组成的路径段,并且最后一个路径段是普通文件名。因此,你不必担心 index.html 和单/双句点的特殊规则。你还可以假设这 $N$ 个路径名中没有两个指向同一个页面。

接下来的 $M$ 对路径名中的每一对都是一个问题:这两个路径名是否指向同一个网页?这些路径名可能包含单句点或双句点,并可能以斜杠结尾。它们可能包含不对应于现有目录或普通文件的名称。

一行中的两个零表示输入的结束。

输出格式

对于每个数据集,你的程序应输出 $M$ 个问题的答案,每个答案占一行。如果两个路径名都指向同一个网页,则每个答案应为 “yes”;如果至少有一个路径名没有指向输入中列出的前 $N$ 个网页中的任何一个,则为 “not found”;否则为 “no”。

样例

输入 1

5 6
/home/ACM/index.html
/ICPC/index.html
/ICPC/general.html
/ICPC/japanese/index.html
/ICPC/secret/confidential/2005/index.html
/home/ACM/
/home/ICPC/../ACM/
/ICPC/secret/
/ICPC/secret/index.html
/ICPC
/ICPC/../ICPC/index.html
/ICPC
/ICPC/general.html
/ICPC/japanese/.././
/ICPC/japanese/./../
/home/ACM/index.html
/home/ACM/index.html/
1 4
/index.html/index.html
/
/index.html/index.html
/index.html
/index.html/index.html
/..
/index.html/../..
/index.html/
/index.html/index.html/..
0 0

输出 1

not found
not found
yes
no
yes
not found
not found
yes
not found
not found

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.