Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re^4: longest common substring

by lima1 (Curate)
on Jan 03, 2008 at 07:24 UTC ( #660131=note: print w/replies, xml ) Need Help??


in reply to Re^3: longest common substring
in thread longest common substring

I think the best exact solutions for the longest common subsequence problem are the dynamic programming ones. But this is only reasonable for 2-4 strings (0(n^2) to O(n^4)). So people use heuristics. A trivial one is to calculate a simple (tree) clustering with something like UPGMA. For example:
$a='AAAB'; $b='AABB'; $c='ABBB'; $d='BBBB'; +---$a +----+ | +---$b | + | | +---$c +----+ +---$d
Then you calculate the subsequences of the leafs (a,b) and (c,d) and in the next step (according some special rules) the subsequences of the subsequences.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://660131]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (7)
As of 2021-04-19 11:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?