The reason why the same offset is seen in strings with a match is because these are biological data.

Are you saying that the substrings you are interested in will always appear at the same offset in both strings?

This is important, because if it is the case, your entire dataset can be processed in under 90 seconds.

P:\test>484593-9 bioman.dat
000:001 L[072]
         (0072,0072)'TTCAGAGACACAGAACCCTGCTCCGACTATTGCCTCTCTCACATCATCA
+A'
000:002 L[1271]
         (1271,1271)'TGCGGAACTCCTTGCAGCTTGTTTCGCTCGCAGCCGGTCTGGAGCGAAA
+C'
000:003 L[225]
         (0225,0225)'AATCCTCACAATACCACAGAGTCTAGACTCGTGGTGGACTTCTCTCAAT
+T'
000:004 L[191]
         (0191,0191)'TCGTGTTACAGGCGGTGTGTTTCTTGTTGACAAAAATCCTCACAATACC
+A'
000:005 L[269]
         (0269,0269)'TCAATTTTCTAGGGGGAACACCCGGGTGTCCTGGCCAAAATTCGCAGTC
+C'
001:002 L[072]
         (0072,0072)'TTCCGGAACAGTAAACCCTGTTCCGACTACTGCCTCACCCATATCGTCA
+A'
001:003 L[072]
         (0072,0072)'TTCCGGAACAGTAAACCCTGTTCCGACTACTGCCTCACCCATATCGTCA
+A'
001:004 L[080]
         (0080,0080)'CAGTAAACCCTGTTCCGACTACTGCCTCACCCATATCGTCAATCTTCTC
+G'
001:005 L[072]
         (0072,0072)'TTCCGGAACAGTAAACCCTGTTCCGACTACTGCCTCACCCATATCGTCA
+A'
002:003 L[320]
         (0320,0320)'CAACCTCCAATCACTTACCAACCTCCTGTCCTCCAACTTGTCCTGGCTA
+T'
002:004 L[191]
         (0191,0191)'TCGTGTTACAGGCGGTGTGTTTCTTGTTGACAAAAATCCTCACAATACC
+A'
002:005 L[269]
         (0269,0269)'TCAATTTTCTAGGGGGAACACCCGGGTGTCCTGGCCAAAATTCGCAGTC
+C'
003:004 L[161]
         (0161,0161)'ACATCACATCAGGACTCCTAGGACCCCTGCTCGTGTTACAGGCGGTGTG
+T'
003:005 L[510]
         (0510,0510)'ACCATGCAAAACCTGCACAACTCTTGCTCAAGGAACCTCTATGTTTCCC
+T'
004:005 L[148]
         (0148,0148)'ATGAACATGGAGAACATCACATCAGGACTCCTAGGACCCCTGCTCGTGT
+T'
 15 trials of bioman.dat ( 27.018ms total), 1.801ms/trial
[download]

That projects to a total time for your 300x3k strings of 80.78 seconds!

There is no trick to that result. Very simple pure perl code that just makes use of the knowledge that the sequences of interest always appear at the same offsets in both strings.

If that is not the case, then a much faster solution will be possible if you can guarentee that all equal-length matching sequences within a given pair will be in the same relative order, even if at different offsets?

To clarify that. Say that there are three equal-length, matching strings (xxx, yyy & zzz) in a given pair of sequences (A & B). If they will always appear such that offset(xxx) < offset(yyy) < offset(zzz) in both A & B. Eg.

A: ....xxx...yyy...zzz
B: xxx....yyy.......zzz....
or
A: .xxx........yyy...zzz.......
b: .............xxx.yyy.zzz
etc.
[download]

Then a much faster solution is possible than the general case where the matching strings might appear in any order.

A: ...xxx...yyy...zzz
B: yyy...xxx...zzz...
[download]

Likewise, if equal-length matching sequences would appear with the same ordering and the same relative offsets:

A: xxx...yyy...zzz...........
B: .....xxx...yyy...zzz......
[download]

That knowledge would also speed up the search considerably.