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

Question

我希望您能用基于正则表达式的JavaScript实现来查找字符串中最长的重复字符串。

我有一个PHP实现，但直接移植到JavaScript后无法工作。

这个PHP实现是从一个回答中获取的，该回答针对问题“查找最长重复字符串”（"Find longest repeating strings?"）：https://dev59.com/yEfYs4cB2Jgan1znAgZ6

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

这将在$input中查找最长的重复子字符串，并将$matches[0][X]（其中X为$matches[0]的长度）填充。我已经测试了许多输入字符串，并确信输出是正确的。

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

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

这不会给出正确的结果

input                  期望的结果       matches[0][X]
======================================================
inputinput             input             input
7inputinput            input             input
inputinput7            input             input
7inputinput7           input             7
XXinputinputYY         input             XX

我对正则表达式不太熟悉，无法理解此处使用的正则表达式在做什么。

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

是否可以修改上述正则表达式，以便在JavaScript中返回预期的输出？我接受这可能不可能在一行内完成。

- Jon Cram

Answer 1

Javascript的matches方法只返回第一个匹配项--你需要循环来查找多个结果。经过一些测试，以下代码可以得到预期的结果：

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”作为返回值，因为它返回了最大长度的第一个字符串。

- Ben Doom

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"]

所以至少使用 match 方法，您会得到 inputinput 作为其中之一的值。显然，这既没有提取最长的部分，也没有去除冗余，但也许仍有帮助。

还有一件事，我在 Firebug 的控制台中进行了测试，它报错说不支持 $1，因此也许有关于 $ 变量值得研究的东西。

- Sid_M