QOJ.ac

QOJ

시간 제한: 2 s 메모리 제한: 64 MB 총점: 100

#13809. 比较代码

통계

Racine Business Networks (RBN) 公司将 Heuristic Algorithm Languages (HAL) 公司告上了法庭,声称 HAL 从 RBN UNIX™ 中窃取了源代码,并将其贡献给了开源操作系统 HALnix。

RBN 和 HAL 都使用一种每行只有一条语句的编程语言,每条语句的格式均为:STOREA = STOREB + STOREC,其中 STOREASTOREBSTOREC 是变量名。具体来说,第一个变量名从第一列开始,后面依次是一个空格、一个等号、一个空格、第二个变量名、一个空格、一个加号、一个空格以及第三个变量名。同一个变量名在同一行中可能会出现多次。变量名由 1 到 8 个大写 ASCII 字母('A'...'Z')组成。

RBN 声称 HAL 直接从 RBN 的源代码中复制了一段连续的行,并且仅进行了微小的修改:

  • RBN 声称 HAL 更改了部分变量名以掩盖其罪行。也就是说,HAL 从 RBN 的程序中取出了一系列行,并将其中每个变量的所有出现都更改为一个新的变量名,尽管新的变量名可能与原变量名相同。当然,没有两个不同的变量会被更改为同一个新变量名。
  • RBN 还声称 HAL 可能改变了某些行等号右侧的顺序:STOREA = STOREB + STOREC 可能会被更改为 STOREA = STOREC + STOREB
  • RBN 声称 HAL 没有改变 RBN 源代码中各行的顺序。

给定 RBN 和 HAL 程序的源代码,找出 HAL 程序中能够通过上述修改由 RBN 程序中的一段连续行得到的、最长的连续行序列的长度。请注意,两个程序中的行序列不需要在两个文件中从相同的行号开始。

输入格式

  • 第一行包含两个空格分隔的整数 $R$ 和 $H$($1 \le R \le 1000$;$1 \le H \le 1000$)。$R$ 是 RBN 程序中源代码的行数;$H$ 是 HAL 程序中源代码的行数。
  • 接下来的 $R$ 行包含 RBN 的程序。
  • 接下来的 $H$ 行包含 HAL 的程序。

输出格式

输出文件应包含单行,其中有一个整数,表示 HAL 可能从 RBN 复制并转换的最长连续行序列的长度。

样例

输入样例 1

4 3
RA = RB + RC
RC = D + RE
RF = RF + RJ
RE = RF + RF
HD = HE + HF
HM = HN + D
HN = HA + HB

输出样例 1

2

说明

如果对 RBN 程序进行以下变量名替换:RA $\to$ HMRB $\to$ DRC $\to$ HND $\to$ HARE $\to$ HB,则 RBN 程序的第 1-2 行与 HAL 程序的第 2-3 行相同。不存在长度为 3 或更多的匹配。

子任务

对于每个使你的程序产生正确输出的测试用例,你都将获得满分。任何测试用例均不给部分分。

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.