поиск макс подстроики очень большого количества строк

@Alpi · Регистрация: 16.11.2012

Студворк — интернет-сервис помощи студентам

Добрый день!

Намекните, пожалуйста, что использовать для поиска максимальной общей подстроки 80 и более строк, каждая из которых состоит из до 1000 символов?
Алфавит фиксированный.

Суффиксные деревья, автоматы, массивы, как я понимаю, тут вообще не подходят...

@Igor3D · 14.01.2013, 11:20

Если общая подстрока - та что входит во все строки, то все просто. Находите все общие в 2 первых строках и помещаете их напр в хеш, можно и в std::set. Для всех остальных строк ищете вхождение каждой подстроки. Отсутствует - удалить из хеша, что останется = результат

@Mysterious Light · 14.01.2013, 13:28

Приведите, пожалуйста, оценку эффиктивности этого алгоритма.

Сразу приходит мысль о том, что в случае почти совпадающих первых двух n-символьных строк в хеше будет ~n(n+1)/2 подстрок, что ~n(n+1)(n+2)/6 байт (n~1000 -> 150 Гб); если в хеше было v строк, то на каждой итерации будет обрабатываться v поисков подстрок, которая тянет минимум на O(n), хотя с алгоритмами поиска подстрок я знаком очень плохо; а поскольку на первой итерации v=O(n^3), уже первая итерация тянет минимум на O(n^4), а всего таких итераций будет по числу строк (минус 2).

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

@Igor3D · 14.01.2013, 16:53

Сообщение от Mysterious Light

Приведите, пожалуйста, оценку эффиктивности этого алгоритма.

Мне кажется лучше подходить к задаче более узко, практично. Напр пусть 1 строка = 1 сообщение этого форума. Тогда никаких громадных данных не видно. Если ввести др разумные ограничения, напр подстрока = слово, или длина подстроки не менее N, то, возможно, размер хеша вообще будет с гулькин нос.

Хорошо, пусть худший случай - теоретик дал такие строки где число совпадающих подстрок огромно. В какой-то момент размер хеша превышает напр миллион. Тогда проверяем текущий хеш по всем строкам. Возможно нам повезет и найдем более длинное совпадение - тогда поиск намного легче. Очишаем хеш и повторяем процесс. Да, вероятно некоторые комбинации будут снова заноситься в хеш - нормальный баланс скорость/расход памяти

Простота реализации - колоссальный фактор. Очень может быть что я предложил совсем не оптимальное решение, но его можно реализовать за пару часов. А у Вас только анализ эффективности займет куда больше времени

@Alpi · 14.01.2013, 22:57 **[ТС]**

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

Возможно, вы правы, но я не до конца понимаю идею с хешами. Что такое более длинное совпадение?

@Igor3D · 14.01.2013, 23:23

Сообщение от Alpi

Возможно, вы правы, но я не до конца понимаю идею с хешами. Что такое более длинное совпадение?

Ну возможно и неправ

Лучше создать N хешей, в первом совпадение 2 символов, во втором 3 и.т.д. Проверка всех строк начинается с самого длинного. Если оно во все строки входит - меньшие хеши уже не нужны - ведь ищем самую длинную.

Насчет огромных данных: ну а если действительно будет мульен совпадений небольшого числа символов? Ничего не попишешь, придется их всех выдавать на гора. А тогда на чем мы хотим экономить?

@Alpi · 14.01.2013, 23:43 **[ТС]**

Тогда никак не поэкономишь.
Я попробую разобраться и сделать на плюсах, хотя для меня это первая по-настоящему сложная задача. но надо же с чего-то начать ))
А подскажете, как быстро найти все общие подстроки двух строк?
Это суффиксным деревом нужно делать?

@Igor3D · 15.01.2013, 18:07

Сообщение от Alpi

А подскажете, как быстро найти все общие подстроки двух строк?
Это суффиксным деревом нужно делать?

Сначала лучше все подготовить - найти хороший класс хеша, отфильтровать повторяющиеся строки, выбрать 2 наименьших строки.

Поиск совпадающих - ну может просто сравнивать 2 массива "сдвигая решетку" и сбрасывать найденное в хеш(и). Да, это тупо и примитивно, но это легко реализовать, так почему бы не попробовать? Подстрока в хеше весит всего 4 байта (2 short), это может компенсировать тупость.

Вообще очень важно (и выгодно) иметь какой-то рабочий вариант, пусть далекий от совершенства, прежде чем, очертя голову, бросаться в дебри деревьев и др.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

@Alpi 104 / 0 / 1 Регистрация: 16.11.2012 Сообщений: 41

	поиск макс подстроики очень большого количества строк 13.01.2013, 23:53. Показов 971. Ответов 7 Метки нет (Все метки) Добрый день! Намекните, пожалуйста, что использовать для поиска максимальной общей подстроки 80 и более строк, каждая из которых состоит из до 1000 символов? Алфавит фиксированный. Суффиксные деревья, автоматы, массивы, как я понимаю, тут вообще не подходят... 0

@Igor3D 1967 / 823 / 114 Регистрация: 01.10.2012 Сообщений: 4,844 Записей в блоге: 2
	14.01.2013, 11:20
	Если общая подстрока - та что входит во все строки, то все просто. Находите все общие в 2 первых строках и помещаете их напр в хеш, можно и в std::set. Для всех остальных строк ищете вхождение каждой подстроки. Отсутствует - удалить из хеша, что останется = результат 0

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,204 Записей в блоге: 24
	14.01.2013, 13:28
	Приведите, пожалуйста, оценку эффиктивности этого алгоритма. Сразу приходит мысль о том, что в случае почти совпадающих первых двух n-символьных строк в хеше будет ~n(n+1)/2 подстрок, что ~n(n+1)(n+2)/6 байт (n~1000 -> 150 Гб); если в хеше было v строк, то на каждой итерации будет обрабатываться v поисков подстрок, которая тянет минимум на O(n), хотя с алгоритмами поиска подстрок я знаком очень плохо; а поскольку на первой итерации v=O(n^3), уже первая итерация тянет минимум на O(n^4), а всего таких итераций будет по числу строк (минус 2). Конечно можно сократить потребляемую память за счёт хранения не подстрок, а ссылок на начало и длину/конец подстроки. Однако вопроса со скоростью для меня открыт. 0

@Alpi 104 / 0 / 1 Регистрация: 16.11.2012 Сообщений: 41
	14.01.2013, 22:57 [ТС]
	Я хотел сделать так же, но не вижу простой реализации, которая не занимала бы огромное время и память. Возможно, вы правы, но я не до конца понимаю идею с хешами. Что такое более длинное совпадение? 0

@Alpi 104 / 0 / 1 Регистрация: 16.11.2012 Сообщений: 41
	14.01.2013, 23:43 [ТС]
	Тогда никак не поэкономишь. Я попробую разобраться и сделать на плюсах, хотя для меня это первая по-настоящему сложная задача. но надо же с чего-то начать )) А подскажете, как быстро найти все общие подстроки двух строк? Это суффиксным деревом нужно делать? 0