Just another Perl shrine | |
PerlMonks |
Re: finding longest common substringby duff (Parson) |
on Nov 19, 2003 at 22:12 UTC ( [id://308424]=note: print w/replies, xml ) | Need Help?? |
One method that might work well enough would be to concatenate the strings and then look for the longest non-overlapping repetition. You'll have to worry about string boundaries though. Here's some code for finding the longest repeated substring in case you take to the idea:
If you joined the strings with some character that won't appear in the strings (a colon say), then you could modify the above such that as soon as you hit a colon, stop Update: I just noticed that you're blindly grabbing the first element in the list. An optimization would be to sort the list of strings by length and always start with the shortest one (assuming you continue using your method). DOH! I just realized that my method won't work at all! Update: Okay ... I'm stubborn. I know it. Here's how to *make* it work with the repeated_substring() routine: Whew! Boy is that inefficient and ugly! :-) revdiablo, you did it well. Don't knock your implementation. Another! update: I realized on my way to pick up the kids that even this method fails. I sure hope revdiablo is watching this to see what could have happened to him :-)
In Section
Seekers of Perl Wisdom
|
|