У меня есть программа, которая может найти самую длинную повторяющуюся подстроку введенной строки, но дело в том, что когда в ответе 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));
Попробуйте заменить вашу функцию 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, тогда вы можете очистить все элементы перед нажатием нового.
Удачного кодирования!
Используя String.prototype.match() и фильтрацию, вы должны получить более короткие совпадения:
const lrs = (s) => s.match(/(.+)(?=.*\1)/g)
.filter((x, _, a) => !a.some((y) => x.length < y.length));
console.info(lrs('123b456k123m456j'));
Условие фильтра с использованием Array.prototype.some()
, вероятно, следует заменить чем-то более производительным, если вы ожидаете большое количество совпадений.
Обновлять
Как упоминалось в комментариях @cars10m, это дает неправильные результаты в случаях, когда часть более длинного повторяющегося шаблона уже используется средством сопоставления регулярных выражений, когда оно соответствует более короткому повторяющемуся шаблону.
Решение состоит в том, чтобы обернуть все выражение в упреждающую группу и продвигать средство сопоставления регулярных выражений по одному символу за раз:
const lrs = (s) => [...s.matchAll(/(?=(.+)(?=.*\1))./g)]
.map(([_,v]) => v)
.filter((x, _, a) => !a.some((y) => x.length < y.length));
console.info(lrs('123456k123m3456j'));
Мне очень нравится этот подход, основанный на регулярных выражениях (+1)! Но, поиграв с ним, я обнаружил, что он не работает со следующей строкой: «123456k123m3456j». Вместо ["3456"] будет возвращено: ["123","456"]. (Я исправил свой первоначальный комментарий.)
Мне это кажется немного пугающим. Спасибо за ответ!
Вау, ты уже получил мой голос - очень впечатляет!
Спасибо. Я учту все ваши советы. Это работает очень хорошо! Большое спасибо!