Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer. OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard. Thanks, Jo?o