代码查重算法

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

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

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

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

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

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

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

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

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

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

输入

输入首先在第一行给出重复代码长度阈值 L_T，为不超过 10 的非负整数。 随后分别给出两段代码，格式为： - 首先在一行中给出代码的文件名，为长度不超过 20 的、仅由英文字母和数字组成的字符串。 - 随后若干行字符为代码内容，最后以 `$` 和一个回车结尾。 题目保证 `$` 不是代码内容的一部分（或可以理解为，只要读到 `$` 和一个回车，其后的内容都不属于这段代码）。题目保证代码内容在经过预处理后不为空，且原始代码不超过 10₃ 个字符。

输出

顺次输出每一轮查到的重复代码片段，每轮次占一行。 在最后一行中顺序输出：第 1 个文件名、第 2 个文件名、两段代码的相似度（输出小数点后 2 位）。数据间以 1 个空格分隔。

样例输入

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 为：

#xxmain(){intx=x;while(x)x--;x<<"xx"<<x;}

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

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

删除重复片段后 C₁ 和 C₂ 更新为：

intx("xx");return

x<<"xx"<<x

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

x"xx"

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