|Welcome to the Monastery|
Re: searching for a pattern using suffix arrays (close)by tye (Cardinal)
|on Oct 08, 2013 at 19:39 UTC||Need Help??|
Your binary search finds an index that matches, not necessarily the first index that matches. So, yes, that was an accidental success. Your loop to search from that point on should stop early, not progress all the way to the end of the list. And your sub isn't properly encapsulated.
Last point first, your code:
indicates that your sub should actually start with something more like:
It would be better design if you didn't access global variables (or file-scoped lexicals) from this sub. To do so, you'd need to pass in at last one more variable.
You can catch this type of error by minimizing the executable code you place at the top level in your script. This is one of the advantages to the style that I still use, (tye)Re: Stupid question.
I don't see a clever way to make a binary search end up stopping on the first match. So I'd just leave your binary search as-is and next march backward until you find the first non-match and then march forward until you find the first non-match in that direction.
I'm guessing that sorting a list of indexes is a recommended approach for making the sorting more efficient (not moving around potentially long strings). But I bet it results in slightly slower Perl code (and more complex code as well).
I'd also remove the '$' entry immediately after populating that list, not after sorting. Or just change the while condition to, for example: