Найти самую большую повторяющуюся подстроку в массиве

Question

Есть массив со строкой в котором нужно найти самую большую подстроку, которая повторяется. Нельзя использовать готовые методы и функции строк.

["abcdgababcefbcdg"] - должно вернуть "bcdg".

Answer 1

Объяснение алгоритма:

Сначала я прохожусь по всей строке и запоминаю для каждого уникального символа все индексы, где они встречаются, в массив
Объявляю пустую строку maxRepeatedSubStr, которая будет возвращена в самом конце
По очереди работаю со сформированными массивами. Если массив длины 1, то я его пропускаю, т.к. это означает, что в строке этот символ единнственный, а значит не может быть 2-х подстрок, которые начинаются с этого символа
В очередном массиве, перебираю всевозможные парные варианты индексов без повторений. Т.е. если я обработал пару (0, 5), то уже (5, 0) не рассматриваю
Смотрю одинаковые ли символы находятся в строке в указанных индексах. Если да, то записваю этот символ в repeatedSubStr и "паралельно" сдвигаю индексы вправо, если нет, то сразу останавливаю цикл. Если нужны подстроки без пересечений, то ограничиваю первый индекс началом второго индекса, если нужны с пересечениями, то просто убираю эту проверку. Второй индекс, всегда ограничивается длиной строки, т.к. второй индекс всегда находится правее перового индекса
После окончания цикла проверяю является ли длина repeatedSubStr больше чем длина maxRepeatedSubStr. Если да, то repeatedSubStr становится новым maxRepeatedSubStr
И так далее пока я не переберу все массивы и всевозможные пары в них без повторений

Без пересечений:

const findMaxRepeatedSubStr = (str) => {
  const lettersMap = new Map();

  for (let i = 0; i < str.length; ++i) {
    const letter = str[i];

    if (lettersMap.has(letter)) {
      lettersMap.get(letter).push(i);
    } else {
      lettersMap.set(letter, [i]);
    }
  }

  let maxRepeatedSubStr = '';

  for(const indexes of lettersMap.values()) {
    if (indexes.length === 1) continue;

    for (let i = 0; i < indexes.length; ++i) {
        for (let j = i + 1; j < indexes.length; ++j) {

          let firstIndex = indexes[i];
          let secondIndex = indexes[j];
          let repeatedSubStr = '';

          while (firstIndex < indexes[j] && secondIndex < str.length) {
            if (str[firstIndex] === str[secondIndex]) repeatedSubStr += str[firstIndex];
            else break;

            ++firstIndex;
            ++secondIndex;
          }

        if (repeatedSubStr.length > maxRepeatedSubStr.length) maxRepeatedSubStr = repeatedSubStr;
      }
    }
  }

  return maxRepeatedSubStr;
}


console.log([
  'abcdgababcefbcdg',
  'ababababab',
  'aaaa',
  'qwerty'
].map((str) => findMaxRepeatedSubStr(str)));

С перечесением:

const findMaxRepeatedSubStr = (str) => {
  const lettersMap = new Map();

  for (let i = 0; i < str.length; ++i) {
    const letter = str[i];

    if (lettersMap.has(letter)) {
      lettersMap.get(letter).push(i);
    } else {
      lettersMap.set(letter, [i]);
    }
  }

  let maxRepeatedSubStr = '';

  for(const indexes of lettersMap.values()) {
    if (indexes.length === 1) continue;

    for (let i = 0; i < indexes.length; ++i) {
        for (let j = i + 1; j < indexes.length; ++j) {

          let firstIndex = indexes[i];
          let secondIndex = indexes[j];
          let repeatedSubStr = '';

          while (secondIndex < str.length) {
            if (str[firstIndex] === str[secondIndex]) repeatedSubStr += str[firstIndex];
            else break;

            ++firstIndex;
            ++secondIndex;
          }

        if (repeatedSubStr.length > maxRepeatedSubStr.length) maxRepeatedSubStr = repeatedSubStr;
      }
    }
  }

  return maxRepeatedSubStr;
}


console.log([
  'abcdgababcefbcdg',
  'ababababab',
  'aaaa',
  'qwerty'
].map((str) => findMaxRepeatedSubStr(str)));

БЛОГ НА HUSL

Найти самую большую повторяющуюся подстроку в массиве

Ответы (1 шт):