C++程序题：代码查重算法

本题请你实现一个简化版的代码查重算法。算法步骤如下：

第 1 步：单词切分。即将代码中连续无间断的若干字母和数字组成的子串定义为一个“单词”。

第 2 步：保留关键词。这里简化为只考虑给定集合 S = {main, return, if, else, for, do, while, int, float, double} 中的词。将代码中除关键词之外的单词都统一替换为单个字母 x。

第 3 步：去掉代码中所有白字符和注释 —— 删除注释比较繁琐，所以本题简化为只删除空格和回车即可。

第 4 步：不妨将前 3 步处理好的两段代码记为 C1 和 C2，它们对应的字符串长度分别为 L1 和 L2。初始化当前重复代码长度 L = 0，记重复代码长度阈值为 LT。重复下述步骤：

（4.1）求两段代码的最长公共子序列，记其长度为 len。若 len > LT，则执行（4.2）；否则执行（4.3）。

（4.2）将最长公共子序列从 C1 和 C2 中删除。将当前重复代码长度 L 增加 len。将 C1 和 C2 更新为剩余的字符串。回去执行（4.1）。

（4.3）计算相似度。相似度定义为 max(L / L1, L / L2)。

注 1：给定序列 X = {x1, x2, … , xn}，其子序列是从该序列中删去若干元素后得到的序列。例如给定 X = {H, E, L, L, O}，则 {E, L, O}、{H, O}、{L} 等均为其子序列。

注 2：当最长子序列匹配不唯一时，首先优先选择 C1 最左边的字符匹配；当 C1 的同一个字符可以匹配多个 C2 中字符时，同样优先选择 C2 最左边的字符匹配。这样保证匹配结果是唯一的。

输入格式

输入首先在第一行给出重复代码长度阈值 LT，为不超过 10 的非负整数。随后分别给出两段代码，格式为：

首先在一行中给出代码的文件名，为长度不超过 20 的、仅由英文字母和数字组成的字符串；
随后若干行字符为代码内容，最后以 $` 和一个回车结尾。题目保证 `$ 不是代码内容的一部分（或可以理解为，只要读到 `$` 和一个回车，其后的内容都不属于这段代码）。题目保证代码内容在经过预处理后不为空，且原始代码不超过 `10^3` 个字符。 **输出格式** 顺次输出每一轮查到的重复代码片段，每轮次占一行。在最后一行中顺序输出：第 1 个文件名、第 2 个文件名、两段代码的相似度（输出小数点后 2 位）。数据间以 1 个空格分隔。 **输入样例** ```text 5 file1 #include<stdio.h> int main() { int tmp=100; printf("hello world"); while(tmp) tmp--; return 0; } $ file2

include<stdio.h>

void main() { int i=10; while(i) i--; cout<<"hello world"<<endl; } $

输出样例

#x<x.x>main(){intx=x;while(x)x--;x;}
file1 file2 0.78

说明提示

样例解释：第一个文件的文件名为 file1。其代码经过前 3 步处理后得到的 C1 为：

#x<x.x>intmain(){intx=x;x("xx");while(x)x--;returnx;}

第二个文件的文件名为 file2。其代码经过前 3 步处理后得到的 C2 为：

#x<x.x>xmain(){intx=x;while(x)x--;x<<"xx"<<x;}

file1 预处理后长度为 53，file2 预处理后长度为 46。第一轮查到的长度为 36 的重复代码片段（即两段代码的最长公共子序列）为：

#x<x.x>main(){intx=x;while(x)x--;x;}

删除重复片段后 C1 和 C2 更新为：

intx("xx");return
x<<"xx"<<x

根据上述更新，第二轮查到的重复代码片段为：

x"xx"

但是因为这个片段长度为 5，没有超过给定的阈值 5，所以不算。最后的重复代码长度为 36。所以相似度为 max(36 / 53, 36 / 46) = 0.78。

限制

时间限制：1000ms，内存限制：64MiB

include<stdio.h>