Поиск наибольшей общей подстроки

172
09 марта 2019, 10:10

Требуется разработать на языке JavaScript код, печатающий на консоль самую длинную общую подстроку всех переданных строк.

Если самая длинная общая подстрока является пустой строкой (например, не было передано ни одной строки или строки не имеют общих для всех символов), напечатать один перевод строки (пустую строку).

При существовании нескольких решений — напечатать одно решение (любое).

Пример:

$ node lcs.js ABCDEFZ WBCDXYZ
CD
$ node lcs.js 132 12332 12312
1
$ node lcs.js ZZZABXXX XXXYYYAB ABYYYZZZ
AB

Код моего скрипта:

function lcs(strings)
{
    let shortest = strings.reduce((a, b) => a.length <= b.length ? a : b);
    let maxlen = shortest.length;
    for (let len = maxlen; len >= 0; len--)
    {
        for (let start = 0; start <= maxlen - len; start++)
        {       
            let substr = shortest.substring(start, len);
            if (strings.every(elem => ~elem.indexOf(substr))) {return substr;}
        }
    }
    return '';
}
if (process.argv.length < 3)
    console.log('');
else
    console.log(lcs(process.argv.slice(2)));

Работает неправильно: когда передаю в качестве параметров следующие строки:

ABCQEFDEFGHIJ BCXEFGYZBCDEWEFGHU

Мой код в консоль печатает D, хотя это не наибольшая общая подстрока.

Советовали использовать регулярные выражения, но с ними не знаком.

Answer 1

Вот так: let substr = shortest.substring(start, start+len);

READ ALSO
Добавление и удаление ячеек через JS

Добавление и удаление ячеек через JS

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

154
Отслеживание ввода и показ сообщения [закрыт]

Отслеживание ввода и показ сообщения [закрыт]

Есть форма на сайте, если пользователь не ввел в течение времени туда никакие данные, показать ему сообщениеКак это реализовать на JS?

147
Несколько кнопок с одинаковой функцией js?

Несколько кнопок с одинаковой функцией js?

Есть окно заказов за годПри нажатии на месяц открывается таблица заказов

187