Необходим найти совпадающие участки в двух битовых массивах, как это сделать?

Question

[Andrean4ik]

Добры вечер!

Мне необходим алгоритм для поиска совпадающих участков в двух битовых массивах.
Гугление и посты на других форумах не помогли.
Если не знаете конкретного ответа, хотя бы посоветуйте литературу где есть смысл поискать, ну и поделитесь своими, даже скромными, идеями.

Заранее благодарю =)

Answer 1

[Станислав Макаров]

Наибольшая общая подпоследовательность

Прям как вам надо.

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

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

Comments

[Andrean4ik]

Спасибо, проблемы с извлечением нету, вопрос только в лучшем способе поиска был =)

[Mrrl]

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

[Станислав Макаров]

Mrrl Похоже, только нужно ужесточить определение от подпоследовательности до подстрок. Методы нахождения аналогичные, добавил ссылку.

Answer 2

[Mrrl]

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