最长的重复子串 JavaScript

Question

我有一个程序可以找到输入字符串的最长重复子串，但问题是，当答案中有 2 个最大长度的重复子串时，我只得到其中一个。

例如，对于字符串 123b456k123m456j，答案是 123，而答案是 123预计 456..

我能以某种方式解决这个问题吗？如果你知道怎么做，请回答我的问题))

let s = prompt('Enter string');

   
function substr(str, begin, end) {
  let result = "";
  for (let i = begin; i < end; i++) {
    result += str[i];
  }
  return result;
}

function lcp(str1, str2) {
  let n = Math.min(str1.length, str2.length);
  for (let i = 0; i < n; i++) {
    if (str1.charAt(i) != str2.charAt(i)) {
      return substr(str1, 0, i);
    }
  }
  return substr(str1, 0, n);
}

function lrs(str) {
  const suffixes = [];
  for (let i = 0; i < str.length; i++) {
    suffixes.push(substr(str, i, str.length));
  }
 
  suffixes.sort();
 
  let result = '';
  let res=[];
  for (let i = 0; i < str.length - 1; i++) {
    const p = lcp(suffixes[i], suffixes[i + 1]);
    if (p.length > result.length){
     result = p;
    }
  }
  return result;
}

alert(lrs(s));

Answer 1

尝试将函数 Los 替换为以下内容。

function lrs(str) {
const suffixes = [];
for (let i = 0; i < str.length; i++) {
    suffixes.push(substr(str, i, str.length));
}

suffixes.sort();

let result = [];
let res = [];
let lastLongestSubStrLen = 0;
for (let i = 0; i < str.length - 1; i++) {
    const p = lcp(suffixes[i], suffixes[i + 1]);
    if (lastLongestSubStrLen <= p.length) {
        result.push(p);
        lastLongestSubStrLen = p.length;
        continue;
    }
}
return result;

}

会成功的！但是，我担心你有嵌套循环。我们需要对其进行优化以提高性能。

请注意，您需要修改我刚刚更改的 if 条件以进行错误处理。另外，我没有检查最坏的情况。例如：第一次出现的重复子串的长度为 2，而下一次的长度为 3，那么您可能希望在推送新元素之前清除所有元素。

编码愉快！

Answer 2

在较短的比赛中使用 String.prototype.match() and filtering 应该可以到达那里：

const lrs = (s) => s.match(/(.+)(?=.*)/g)
                    .filter((x, _, a) => !a.some((y) => x.length < y.length));

console.log(lrs('123b456k123m456j'));

如果您希望有大量匹配项，使用 Array.prototype.some() 的过滤条件可能应该换成性能更好的条件。

更新

正如@cars10m 在评论中提到的，如果较长的重复模式的一部分在匹配较短的重复模式时已被正则表达式匹配器消耗，则这会产生不正确的结果。

解决方案是将整个表达式包装到一个前瞻组中，并一次将正则表达式匹配器推进一个字符：

const lrs = (s) => [...s.matchAll(/(?=(.+)(?=.*))./g)]
                   .map(([_,v]) => v)
                   .filter((x, _, a) => !a.some((y) => x.length < y.length));

console.log(lrs('123456k123m3456j'));

最长的重复子串 JavaScript

The longest repeating substrings JavaScript

javascript

string

longest-substring