使用正则表达式在 JavaScript 中查找最长重复子字符串

Question

我想找到字符串中最长的重复字符串，用 JavaScript 实现并使用基于正则表达式的方法。

我有一个 PHP 实现，当直接移植到 JavaScript 时，它不起作用。

PHP 实现取自问题“查找最长重复字符串？” 的答案

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

：将使用最长的重复子字符串填充 $matches[0][X]（其中 X 是 $matches[0] 的长度）可以在 $input 中找到。我已经用许多输入字符串对此进行了测试，并且确信输出是正确的。

JavaScript 中最接近的直接端口是：

var matches = /(?=((.+)(?:.*?\2)+))/.exec(input);

这不会给出正确的结果

input                  Excepted result   matches[0][X]
======================================================
inputinput             input             input
7inputinput            input             input
inputinput7            input             input
7inputinput7           input             7
XXinputinputYY         input             XX

我对正则表达式不够熟悉，无法理解此处使用的正则表达式的作用。

我当然可以实现一些算法来找到最长的重复子串。在尝试这样做之前，我希望不同的正则表达式能够在 JavaScript 中产生正确的结果。

是否可以修改上述正则表达式，以便在 JavaScript 中返回预期的输出？我承认这在一句台词中可能是不可能的。

Answer 1

Javascript 匹配仅返回第一个匹配项——您必须循环才能找到多个结果。一些测试表明这得到了预期的结果：

function maxRepeat(input) {
 var reg = /(?=((.+)(?:.*?\2)+))/g;
 var sub = ""; //somewhere to stick temp results
 var maxstr = ""; // our maximum length repeated string
 reg.lastIndex = 0; // because reg previously existed, we may need to reset this
 sub = reg.exec(input); // find the first repeated string
 while (!(sub == null)){
  if ((!(sub == null)) && (sub[2].length > maxstr.length)){
   maxstr = sub[2];
  }
  sub = reg.exec(input);
  reg.lastIndex++; // start searching from the next position
 }
 return maxstr;
}

// I'm logging to console for convenience
console.log(maxRepeat("aabcd"));             //aa
console.log(maxRepeat("inputinput"));        //input
console.log(maxRepeat("7inputinput"));       //input
console.log(maxRepeat("inputinput7"));       //input
console.log(maxRepeat("7inputinput7"));      //input
console.log(maxRepeat("xxabcdyy"));          //x
console.log(maxRepeat("XXinputinputYY"));    //input

请注意，对于“xxabcdyy”，您只能返回“x”，因为它返回最大长度的第一个字符串。

Answer 2

JS 正则表达式似乎有点奇怪。我没有完整的答案，但这是我发现的。

虽然我认为他们做了同样的事情 re.exec() 和 "string".match(re) 的行为不同。 Exec 似乎只返回它找到的第一个匹配项，而 match 似乎返回所有匹配项（在两种情况下都使用 /g）。

另一方面， exec 似乎可以与正则表达式中的 ?= 一起正常工作，而 match 返回所有空字符串。删除 ?= 留给我们

re = /((.+)(?:.*?\2)+)/g

使用

"XXinputinputYY".match(re);

返回

["XX", "inputinput", "YY"]

而

re.exec("XXinputinputYY");

返回

["XX", "XX", "X"]

所以至少在匹配时你得到 inputinput 作为你的值之一。显然，这既没有拉出最长的，也没有消除冗余，但也许它仍然有帮助。

另一件事，我在 firebug 的控制台中进行了测试，它抛出了一个关于不支持 $1 的错误，所以也许 $ 变量中有一些值得一看的东西。