Re^3: Search for identical substrings

The problem is that the "LCS" in Algorithm::Diff is Longest Common Sub-Sequence, but for your requirements you need Longest Common String.

The difference being the latter is contiguous, whilst the former is not (need not be).

You're after this?

P:\test>lcs "banana is split" "banana..s split"
banana is split
banana..s split
        s split
[download]

I'm still verifying my algorithm is correct, but so far it appears to be about 10x quicker than the XS version of LCSS despite being pure perl.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.

Comment on Re^3: Search for identical substrings Download Code

Replies are listed 'Best First'.
Re^4: Search for identical substrings by bioMan (Beadle) on Aug 19, 2005 at 16:50 UTC
You are correct I want the string "s split". Per GrandFather's request I'll try to put some real data into my scratchpad later today.	[reply]


XP is just a number
	PerlMonks