Эффективное сопоставление подстрок в perl

Я ищу эффективное решение для поиска максимально длинной подстроки в строке, допускающей несовпадения n в основной строке

Например: Основная строка

1. AGACGTAC TACTCTACT AGATGCA * TACTCTAC *
2. AGACGTAC TACTCTACT AGATGCA * TACTCTAC *
3. AGACGCA * TACTCTAC *
4. AGACGCA2 * TAC85 [1114] TACTC62] TACTC62 [1114851] AGACGTC62 [1114 * TAC] [1114] AGACGTAC TACTTTACA AGATGCA * TACTCTAC *

Строка поиска:

1. TACTCTACT: это следует рассматривать как соответствие всем вышеперечисленным основным строкам.

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

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

PS: У меня будет одна строка поиска и около 100 миллионов основных строк для найдите в подстроке строку.

Спасибо! -Abhi