Всем доброго времени суток, мне нужен алгоритм на javascript (желательно готовый), который позволит определять совпадения в двух подстроках, то есть например, есть две такие строки:
Abcdefg и cdelmn и что бы алгоритм выбирал совпадающие части, то есть cde, заранее благодарю за помощь)
Доброго и вам времени суток, встречал похожий вопрос, вот вариант реализации с объяснением участков кода:
<div id="results">
function search_largest_substr(){
/*
Наибольшая общая строка не может
быть больше наименьшей входной строки.
Находим наименьшую и по ходу формируем
массив с остальными:
*/
// в эту переменную внесем самую маленькую подстроку
let str_min = arguments[0];
// сюда сложим все остальные подстроки
const list = [];
// пробежим в цикле по всем переданным в функцию аргументам
for(let n=1; n<arguments.length; n ){
// если строка в str_min меньше чем в
if(str_min.length<arguments[n].length){
// вносим в list текущую строку
list.push(arguments[n]);
// переходим к следующей итерации цикла
continue;
}
// иначе в list строку, лежащую в str_min
list.push(str_min);
// запоминаем в str_min текущую строку
str_min = arguments[n];
}
/*
Далее нам надо проверить наличие всех возможных
подстрок из самой маленькой строки в других строках.
Например если самая маленькая подствока была "abcd"
то надо последовательно проверить
"abcd", "abc", "bcd", "ab", "bc", "cd", "a", "b", "c", "d"
Но при этом, как только будет найдена подстрока имеющаяся
во всех строках надо сразу завершить цикл с проверкой.
*/
// Данный цикл будет определять текущий размер
// проверяемой подстроки, начиная от наибольшего возможного.
// Например для строки "abcd" это будут значения 4, 3, 2, 1
for(let l=str_min.length; l>0; l--){
// В данном цикле определяем позицию подстроки.
// Например для строки "abcd" это будут значения:
// при l=4 будут 0
// при l=3 будут 0, 1
// при l=2 будут 0, 1, 2
// при l=1 будут 0, 1, 2, 3
for(let p=0; p<str_min.length-l; p ){
// берем из наименьшей строки тестируемую подстроку
const substr = str_min.slice(p, p l 1);
// если искомый фрагмент есть во всех строках
// то isFound будет присвоено true
let isFound = true;
// далее в цикле проверяем все остальные строки
// на наличие искомой подстроки
for(let i=0; i<list.length; i ){
// если искомая подстрока присутствует в
// текущей строке - ничего не делаем
if( list[i].indexOf(substr) >= 0)
continue;
// иначе выставляем isFound=false
// и прерываем текущий цикл по i
isFound=false;
break;
}
// если isFound == true значит нужная подстрока найдена
if( isFound )
return substr;
// иначе продолжаем поиск
}
}
// если не было найдено ни единой соврадающей подстроки
// возвращаем пустую строку
return "";
}
// Тестируем:
const results = document.getElementById("results");
var str = search_largest_substr("ABCDEFGH", "ABCDEFG", "ABCDEF");
results.innerHTML = '
в строках ("ABCDEFGH", "ABCDEFG", "ABCDEF") найдена общая подстрока
"' str '"';
str = search_largest_substr("123445", "12654", "123768");
results.innerHTML = '
в строках ("123445", "12654", "123768") найдена общая подстрока
"' str '"';
str = search_largest_substr("ABCD", "WBCDX");
results.innerHTM = '
в строках ("ABCD", "WBCDX") найдена общая подстрока
"' str '"';