Самые длинные повторяющиеся подстроки JavaScript

У меня есть программа, которая может найти самую длинную повторяющуюся подстроку введенной строки, но дело в том, что когда в ответе 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));
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
2
0
1 856
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Попробуйте заменить вашу функцию 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, тогда вы можете очистить все элементы перед нажатием нового.

Удачного кодирования!

Спасибо. Я учту все ваши советы. Это работает очень хорошо! Большое спасибо!

Alice 20.12.2020 16:09

Используя 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"]. (Я исправил свой первоначальный комментарий.)

Carsten Massmann 20.12.2020 15:59

Мне это кажется немного пугающим. Спасибо за ответ!

Alice 20.12.2020 16:11

Вау, ты уже получил мой голос - очень впечатляет!

Carsten Massmann 20.12.2020 21:21

Другие вопросы по теме