Don't ask to ask, just ask | |
PerlMonks |
Re^2: Longest Common Subsequenceby Limbic~Region (Chancellor) |
on May 16, 2006 at 19:47 UTC ( [id://549876]=note: print w/replies, xml ) | Need Help?? |
If you understood the mental process I went through to create the Longest Common Subsequence, it should not be hard to see how to adapt it to the Longest Common Substring. Once we have a list of character positions across strings, we can create ordered piles where each mapping has a difference of 1 in each position with its adjacent neighbors. You can get rid of the need for looping to find mappings greater because you can predict the values they should contain. Then you just need to find the largest pile and that represents the LCS (S = substring). Arrays are replaced with hashes. Picking a hash key at random, you place it in a new pile and then predict the next mapping. If that key exists you place it on the same pile. You repeat this process until you have no more mappings. You then start back at the beginning of the pile and look for smaller items. Once no more items fit in that pile, you move on to the next hash key.
Cheers - L~R
In Section
Meditations
|
|