Find the overlap of a set of equal length string?

Question

There are 1 million of equal length strings(short string).For example

abcdefghi

fghixyzyz

ghiabcabc

zyzdddxfg

. . .

I want to find pair-wise overlap of two string.The overlap of A"abcdefghi" and B"fghixyzyz" is "fghi",which is the maximal suffix of A , the maximal prefix of B ,satisfy the suffix and the prefix are equal.

Is there efficient algorithm which can find the overlap of any two strings in the set?

So by overlap you mean the suffix of one is equal to the prefix of other? — sukunrt, May 25 '12 at 08:58
I think this question would be helpful. http://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap — sukunrt, May 25 '12 at 09:00

score 0 · Answer 1 · answered Sep 08 '12 at 13:40

One of the efficient ways is to build a general suffix tree for the string set. To find the overlap between string x and y:

Follow the path label for string y in the general suffix tree. The deepest node along this path that is incident to the terminal symbol of string x has a path label which is equivalent to the suffix-prefix overlap x->y.

For more details see page 137 ("Solving the all-pairs suffix-prefix problem in linear time") of Gusfield's book "Algorithms on Strings, Trees, And Sequences".

Caution: this uses a LOT of memory if your dataset is large (millions/billions of strings).

Find the overlap of a set of equal length string?

1 Answers1