Алгоритм помогите! Быстрый алгоритм поиска строки с партнером
Я ищу быстрый алгоритм для поиска в огромной строке (это последовательность генома организма, состоящая из сотен миллионов миллиардов символов).
В этой строке присутствует только 4 символа {A, C, G, T}, и «A» может соединяться только с «T», а «C» - с «G».
Теперь я ищу две подстроки (с ограничением длины обеих подстрок между {minLen, maxLen} и длиной интервала между {intervalMinLen, intervalMaxLen}), которые могут соединяться друг с другом антипараллельно.
Например, строка: ATCAG GACCA TACGC CTGAT
Ограничения: minLen = 4, maxLen = 5, intervalMinLen = 9, intervalMaxLen = 10
Результат должен быть
"ATCAG" пара с "CTGAT"
"TCAG" пара с "CTGA"
Заранее спасибо.
Обновление: у меня уже есть метод, чтобы определить, могут ли две строки соединяться друг с другом. Единственная проблема заключается в том, что полный поиск занимает очень много времени.