Estoy buscando un algoritmo rápido para fines de búsqueda en una cadena enorme (es una secuencia del genoma del organismo compuesta de cientos de millones a miles de millones de caracteres).

Solo hay 4 caracteres {A, C, G, T} presentes en esta cadena, y "A" solo puede emparejarse con "T" mientras que "C" se empareja con "G".

Ahora estoy buscando dos subcadenas (con la restricción de longitud de ambas subcadenas entre {minLen, maxLen} y la longitud del intervalo entre {intervalMinLen, intervalMaxLen}) que pueden emparejarse entre sí de forma antiparalela.

Por ejemplo, la cadena es: ATCAG GACCA TACGC CTGAT

Constraints: minLen = 4, maxLen = 5, intervaloMinLen = 9, intervaloMaxLen = 10

El resultado debería ser

"ATCAG" se empareja con "CTGAT"

"TCAG" se empareja con "CTGA"

Gracias por adelantado

Update: ya tengo el método para determinar si dos cadenas pueden emparejarse entre sí. La única preocupación es hacer una búsqueda exhaustiva que consume mucho tiempo.