如何用正则表达式查找可重叠的最长重复子串？

咱们先聊聊你原来的代码为啥没得到预期结果，再一步步写出能支持重叠重复子串的实现。

原代码的问题分析 #

你的正则/(.+)(?=.*\1)/gi逻辑是找后面存在相同副本的子串，但这里的.*是贪婪匹配，会跳过中间的所有字符，导致它只能捕捉到非重叠的重复子串，完全没法处理重叠的情况。比如在你的输入里，预期的"is thi"是需要通过重叠匹配逻辑才能被检测到的，但原正则会优先找到更长的非重叠子串（或者因为回溯机制的限制，找不到更长的重叠子串），最终返回了"is th"。

另外，这个正则的匹配结果依赖于正则引擎的回溯顺序，没法保证枚举所有可能的重复子串，自然也选不到真正最长的那个。

用正则实现支持重叠的最长重复子串的方案 #

思路很清晰：从最长的可能子串长度开始，依次检查每个长度的子串是否存在至少两次出现（允许重叠），找到第一个符合条件的子串就是我们要的结果。

具体实现步骤：

1. 先把输入字符串转成小写，统一处理大小写问题。
2. 从最大可能的子串长度（字符串长度-1，因为至少要出现两次）开始，往下遍历到长度1。
3. 对每个长度L，用正则提取所有长度为L的子串（包括重叠的），通过维护一个集合来检查是否有重复的子串。
4. 一旦找到重复的子串，直接返回它（因为我们是从最长到最短遍历的，第一个找到的就是最长的）。

完整代码 #

function findLongestRepeatedSubstring(input) {
  const lowerStr = input.toLowerCase();
  // 从最长可能的子串长度开始检查，至少要出现两次
  for (let length = lowerStr.length - 1; length >= 1; length--) {
    const regex = new RegExp(`(.{${length}})`, 'g');
    const seenSubstrings = new Set();
    let match;
    
    // 重置正则的lastIndex，避免循环中出现异常
    regex.lastIndex = 0;
    
    while ((match = regex.exec(lowerStr)) !== null) {
      const currentSub = match[1];
      // 如果这个子串已经见过，说明找到了重复的，直接返回
      if (seenSubstrings.has(currentSub)) {
        return currentSub;
      }
      seenSubstrings.add(currentSub);
      // 移动到下一个字符，开启重叠匹配
      regex.lastIndex = match.index + 1;
    }
  }
  // 如果没有找到重复子串，返回空字符串
  return '';
}

// 测试你的输入
const x = "Is this thing on?";
console.log(findLongestRepeatedSubstring(x)); // 输出: "is thi"

关键细节解释 #

• 重叠匹配的实现：默认情况下，正则的exec方法会从上次匹配结束的位置开始下一次匹配（lastIndex会自动设置为match.index + match[0].length）。我们手动把lastIndex改成match.index + 1，这样每次匹配后只移动一个字符，就能捕捉到重叠的子串。
• 从长到短遍历：这样我们可以在找到第一个重复子串时直接返回，不用再检查更短的子串，效率更高。

内容的提问来源于stack exchange，提问作者Andre Marasca