Как найти общие подстроки в нескольких строках на JavaScript?

Здравствуйте, мне необходима помощь в составлении алгоритма. Я хочу создать скрипт, который выводит одинаковые последовательности символов (то бишь подстрок) в нескольких строках. Строки рандомные, то есть их вводит пользователь. Например:
"ABCD" "WBCDX"
Ответ : BCD.
"123445" "12654" "123768"
Ответ: 12
"ABCDEFGH" "ABCDEFG" "ABCDEF"
Ответ: "ABCDE"
Зараннее огромное спасибо за помощь!

До этого мог находить только заданную подстроку в одной строке, с этим случаем я справиться пока не могу.
  • Вопрос задан
  • 6791 просмотр
Решения вопроса 2
lastuniverse
@lastuniverse
Всегда вокруг да около IT тем
Есть более простое (алгоритмически) решение.
Общая суть его такова, вместо построения матрицы N1 x N2 делаем последовательный сдвиг меньшей строки относительно большей (1 цикл длинной N1+N2-2). На каждой итерации этого сдвига делаем второй цикл через текущую область пересечения этих строк, подсчитывая совпадения символов и запоминая их, если число совпадений больше предыдущего. Так же время выполнения такого алгоритма будет не O(Nmax*Nmin) а O(Nmax*Nmin -Nmin)

Если не поленюсь, оформлю с утра в виде кода)

PS: Заставляете не полениться:) Для поддержки поиска по строкам в количестве больше 2-х алгоритм был несколько модифицирован. Для удобства понимания почти не использовал "особые фишки" JavaScript-а, все выполнено на обычных циклах.
код с комментариями

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);

				// если искомый фрагмент есть во всех строках
				// то 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 "";
}


// Исползуем функцию поиска так:
var str = search_largest_substr("ABCDEFGH", "ABCDEFG", "ABCDEF");
console.log(str);


str = search_largest_substr("123445", "12654", "123768");
console.log(str);


Ответ написан
@DanKud
var arr = [ /* массив со строками */
	'THREE',
	'DIFFERENT',
	'LINES'
]

function compare(inStr, cStr) { /* фукнция сравнения двух строк на наличии одинаковых символов */
	var result = inStr.split('').filter(function(letter) {
	  return (cStr.indexOf(letter) > -1);
	});
	return result;
}

for (i = 0; i < (arr.length-1); i++) { /* перебираем циклом строки из массива */
	var result = (i == 0) ? compare(arr[i], arr[i+1]) : compare(result.join(''), arr[i+1]);
}

var finalStr = result.join(''); /* преобразуем полученный массив в строку */

/* если нужно убрать повторяющиеся символы используем нижеприведенный метод для вывода результата
var finalStr = Array.from(new Set(result)).join('');
*/

alert(finalStr);
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Прямой поиск:
И обратный поиск:
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
18 апр. 2024, в 21:56
2000 руб./за проект
18 апр. 2024, в 21:00
150 руб./за проект