找到最长的重复字符串？

Question

我有一些HTML/CSS/JavaScript,带有痛苦的长类,id,变量和函数名称以及其他被反复使用的组合字符串.我可以重命名或重组其中的一些并将文本切成两半.

所以我正在寻找一种简单的算法来报告文本中最长的重复字符串.理想情况下,它会按长度乘以实例进行反向排序,以突出显示字符串,如果全局重命名,则会产生最大的节省.

这感觉就像我在100行代码中痛苦地做的事情,其中​​有一些优雅的10行递归正则表达式.这听起来像是一个家庭作业问题,但我向你保证不是.

我在PHP工作,但很乐意看到任何语言的东西.

注意:我不是在寻找HTML/CSS/JavaScript缩小本身.我喜欢有意义的文字,所以我想亲自去做,并且要比较臃肿.

Answer 1

这将找到所有重复的字符串:

(?=((.+)(?:.*?\2)+))

使用它preg_match_all并选择最长的一个.

function len_cmp($match1,$match2) {
  return $match2[0] - $match1[0];
}

preg_match_all('/(?=((.+)(?:.*?\2)+))/s', $text, $matches, PREG_SET_ORDER);

foreach ($matches as $match) {
  $match[0] = substr_count($match[1], $match[2]) * strlen($match[2]);
}

usort($matches, "len_cmp");

foreach ($matches as $match) {
  echo "($matches[2]) $matches[1]\n";
}

这种方法可能会很慢,因为可能会有很多字符串重复.您可以通过指定模式中的最小长度和最小重复次数来减少它.

(?=((.{3,})(?:.*?\2){2,}))

这将限制重复至少三个的字符数,并将重复次数限制为三个(第一个+2个).

编辑:更改为允许重复之间的字符.
编辑:更改排序顺序以反映最佳匹配.