考虑到如下的两段代码,很容易发现他们其实是一样的。
代码1
int i, j;
i = 3;
j = i + 1;
代码2
int a, i;
a = 3;
i = a + 1;
这是因为这两段代码之间唯一的差异,只是他们更换了一下变量名,比如第
一段代码中的i变成了第二段的a,第一段的j变成了第二段的i。而其他的常量,
例如3,1或者其他的关键字和运算符,比如 int,+和;。都是没有发生变化的。
不过注意到如下的代码片段,我们并不能简单认为这是一样的,因为这不是
一个简单的替换,而是可以导致不同运算结果的。
代码3
a = 3;
b = 3;
代码4
c = 3;
c = 3;
为了简化问题,我们用大写字母来表示所有的关键字、常量等非变量符合。
假如我们采用如下的替换表
那么最开始给出的两段雷同代码就可以分别写成 AiBjCiDECjDiFGC 以及
AaBiCaDECiDaFGC。或者简单的说,我们认为这两段代码是一样的。
现在请写一个程序,处理若干这样的代码雷同检测问题:给一个完整代码以
及一个较短的代码片段,请求出,这个代码片段在完整代码中一共出现了多少次
(代码片段出现的位置可以重叠)。
为了简单起见,我们认为程序中只会至多出现 a~z 这 26 个变量,同时也至
多只有A~Z这26个非变量符号。