Если входная строка может иметь любую значительную длину или производительность вообще беспокоит, то один из лучших способов решить эту проблему - не с помощью регулярных выражений, а с более сложной структурой строковых данных, которая облегчает эти виды запросов гораздо эффективнее.
Такая структура данных представляет собой дерево суффиксов . Для строки S ее суффиксное дерево по существу является Patricia trie всех ее суффиксов. Несмотря на кажущуюся сложность, он может быть построен за линейное время.
Дерево суффиксов для "BANANA" (любезно предоставлено Википедией)
С суффиксным деревом можно действительно эффективно выполнять многие виды запросов, например, поиск всех вхождений подстроки, самой длинной подстроки, которая встречается как минимум дважды, и т. д. Тип строк, которые вы ищете, называется , тандем повторяется . Чтобы упростить этот запрос, вам необходимо предварительно обработать дерево суффиксов за линейное время, чтобы вы могли выполнять запросов с наименьшим общим предком в постоянное время.
Эта проблема очень распространена в вычислительной биологии, где ДНК можно рассматривать как строку VERY длиной, состоящую из букв в ACGT. Таким образом, производительность и эффективность имеют первостепенное значение, и эти очень сложные алгоритмы и методы были разработаны.
Вы должны изучить реализацию этих методов с нуля для вашей двоичной последовательности, или, возможно, проще сопоставить вашу двоичную последовательность с "поддельной" цепочкой ДНК, а затем использовать один из многих инструментов, доступных для исследования генов.
Смотри также