data-code-C.doc

Competition Day One August 18, 2003 Comparing Code Comparing Code (代码比较)题目Racine商用网络公司（RBN）将启发式算法语言（HAL）公司告上法庭，RBN宣称HAL公司已将RBN UNIXTM 中的源代码扩散到开放式源代码操作系统HALnix 中。RBN和HAL公司都使用同一种程序设计语言，该语言每行只有一个语句，语句的形式如下： STOREA STOREB STOREC，其中STOREA 、STOREB 和STOREC都是变量名。而且，第一个变量名从第一列开始，后面紧跟一个空格，一个等号，一个空格，然后是第2个变量名，一个空格，一个加号，一个空格，最后是第3个变量名。同一个变量名在一行里可以出现多于一次。变量名由1到8个大写字母 AZ组成。RBN宣称HAL公司直接从RBN 的源代码中复制了一串连续的程序行，对这段程序仅做了以下几点微不足道的修改：l RBN称HAL公司为掩饰其丑行而对程序中的变量名进行了修改。换句话说，HAL公司从RBN的程序中复制了一段连续的程序行，并将其中的每个变量名改变为一个新的变量名，尽管这个新的变量名也可能与原变量名相同。当然，原来两个不同的变量名不会改为同一个新的变量名。l RBN还声称HAL公司可能还改变了一些程序行中等号右端的变量次序，如：STOREA STOREB STOREC可能被修改为STOREA STOREC STOREB。l RBN称HAL公司并未改动RBN 的源代码的程序行顺序。给出RBN和HAL公司的源代码程序，要求你从HAL公司的程序中找出使用上述修改可能取自RBN程序的最长连续的程序行。需注意的是来自两个公司源代码的连续程序行在两个文件中并不需要在相同的行号开始。输入文件：code.inl 输入文件的第一行包含用空格分隔的两个整数，R和H（1 R 1000；1 H 1000）。 R是RBN源代码程序的行数。l 随后的R行是RBN的源代码程序l 紧接着的H行是HAL公司的源代码程序输出文件：code.out 输出文件仅包含一行，该行有一个整数，给出HAL公司可能复制RBN源代码的最长连续的程序行的长度（行数）。样例输入文件：4 3RA = RB + RCRC = D + RERF = RF + RJRE = RF + RFHD = HE + HFHM = HN + DHN = HA +HB样例输出文件：2如果对RBN程序的变量名进行如下替换：RAHM，RBD，RCH，NDHA，REHB，则RBN程序的第12行与HAL公司程序的第23行内容相同。但不存在大于2行以上的类似匹配。资源限制运行时间（CPU）2秒内存64MB记分规则对于每个测例如果你的程序能够产生正确的输出文件则该例得满分。没有测例能够获得部分分（意味着对于每个测例或者得满分或者得零分）。算法设计与分析可将该问题分解为两个步骤：首先确定是否存在从第一个程序的部分语句行集合到第二个程序的部分语句行集合的映射（称解决这一步骤的算法为内部算法）。然后确定满足该映射的最佳范围（称解决这一步骤的算法为外部算法）。外部算法的效率取决于内部算法所提供的功能。任给两个语句行的集合，应能十分有效地计算出从其中一个完整的集合到另一个集合是否存在一个变量映射。这里将每一行看作一个方程。一个方程的对应方程指的是在另一个程序中位于相同行的那个方程。对于每个程序中所涉及的每个变量，考查该变量在这个程序中出现的所有行。如果该变量曾经出现在等式的左端，那么这个变量必定被映射到另一个程序对应方程的左端的相应位置。如果该变量在某方程的右端出现两次，那么它必定与另一个程序对应方程的右端的相应变量相匹配（并且这个对应方程也必须使用同一变量）。如果一个变量仅仅出现在一个程序的方程右端，那么这个变量在对应方程相应右端的所有出现也一定共享一个公共的变量。很明显，不存在将一个变量映射为两个不同变量的情形。如果已知变量X的映射是Y，那么若X的任一个出现都没有在对应方程中找到Y，那么这个X到Y的映射也就根本不存在。注意两个程序中的变量必须都加以测试。所有上述这些条件都是必要的，同时更要清楚它们也是充分的。如果由上述条件，变量X必须映射到另一个变量Y，那么通过上述条件的测试来保证变量X的每次出现都能映射到变量Y。注意变量X已知映射到变量Y当且仅当变量Y已知映射到变量X。如果变量X能够匹配到变量Y或者变量Z（YZ），那么可能有这样几种情形：变量Y或者变量Z的映射均未知；变量Y或者变量Z两者之一的映射已知；变量Y和变量Z两者的映射均已知。下面分别加以分析。第一种情形两者均未知：如果变量Y或者变量Z的映射均未知，那么变量Y或者变量Z的每次出现，一定出现在一个方程的右端。此外，对应方程的右端一定是X和某个其它变量W。因而这两个变量能够以任一种方式映射。第二种情形两者之一已知：如果变量X能够映射到变量Y或者映射到变量Z，那么存在某一行使得变量X和某个变量W可能映射到变量Y或者变量Z。不失一般性，假设Y的映射已知。因为（如果）Y不能映射到X，它必须映射到W，或者这些条件将会丢弃这个程序集。因为变量Z的映射是未知的，那么它就不会出现在任一个其它位置或者总是与X和W配对出现。这样，X能够被映射到Z，反之亦然。第一种情形两者均已知：如果变量X能够映射到变量Y或者变量Z，那么存在某一行使得变量X和某个变量W可能映射到变量Y或者变量Z。如果Y和Z的映射均已知，那么它们一定映射到那个变量W，两种情形都不合法，并且将被上面的条件发现或截获。为方便以下分析，不失一般性，不妨假设RH。算法算法要点时间复杂性得分1对于从R到R的每一行，从不同于所希望的offset第一行开始。试图将该行加到每个子程序的末尾。如果一对行不能被加入，从子程序的开始删去行对直到该行对能够加入或该子程序为空。O（R H）假定这些条件可以用O（1）时间增量式地检查。它需要一种方法能够增量式地更新条件，包括在子程序末尾增加一些行以及在子程序的开始删去一些行。1002从每个程序各取一行开始，试图将该行加到每个子程序的末尾，直到出现冲突为止O（R2 H）假定这些条件可以用O（1）时间增量式地检查。它需要一种方法能够增量式地更新条件，在子程序末尾增加一些行653对于每一对开始位置，考虑每一个与之配对的开始位置的可能的程序，通过二分搜索寻找最优长度O（R2 H logR）假定检查一个映射的存在性能够用行数的线性时间来完成。该方法不需要支持增量式操作55%4代替O（1）时间的映射检查，使用最大加权两部匹配。在每对变量名之间加一条边，其权值取它们配对的数目。如果最大加权两部匹配是3k，其中k是所考虑的子程序的行数，则存在一个映射。取决于所使用的外部算法，同时随算法实现的情形变化。45%5尝试通过所有可能映射的受限搜索构造一个变量映射所使用的算法不同，其有效性差别很大。30%测试数据Test#PointsRHAnswer15444255443596045544551233651011752001028590704395125110401051801706