in reply to Intersecting Two Strings

for additional info about the problem see Longest common substring, which explains the runtime of several algorithms.

Replies are listed 'Best First'.
Re^2: Intersecting Two Strings
by goibhniu (Hermit) on Aug 22, 2007 at 14:27 UTC

    A quick search of CPAN turns up: String::LCSS, though I've never used it. There were several other hits as well.

    I humbly seek wisdom.
[reply]
Re^2: Intersecting Two Strings
by lima1 (Curate) on Aug 22, 2007 at 12:38 UTC
    It seems that OP's problem is an easy special case of the LCS problem. We have one big string S and 2 substrings (seq1, seq2) with known coordinates within S: 
    S:    CTGCCACCGCTGTGTTTCGGCCGGCGAXXXXXXXXXXXXXXXXXXXXX
seq1: CTGCCACCGCTGT (Pos: 0)
seq2:      ACCGCTGTGTTTCGGCCGGCGA (Pos: 5)

    [download]
    So it's a trivial O(1) algorithm to calculate the overlap with the substring positions and lengths.
[reply]
[d/l]

In Section Seekers of Perl Wisdom