[Okular-devel] [okular] [Bug 323263] New: Search fails if backtracking needed

[Jaan Vajakas]

https://bugs.kde.org/show_bug.cgi?id=323263

            Bug ID: 323263
           Summary: Search fails if backtracking needed
    Classification: Unclassified
           Product: okular
           Version: 0.17.60
          Platform: Compiled Sources
                OS: Linux
            Status: UNCONFIRMED
          Severity: normal
          Priority: NOR
         Component: general
          Assignee: okular-devel at kde.org
          Reporter: jaanvajakas at hot.ee

Looking at the implementation of TextPagePrivate::findTextInternalForward and
TextPagePrivate::findTextInternalBackward in textpage.cpp, it seems that no
backtracking is done, which can sometimes make the search fail. E. g. if the
user searches for "ab" and the document consists of the string "aabaab" then
Okular detects that the first "a" in "aabaab" matches the first letter in "ab",
but the first two letters "aa" in "aabaab" do not match "ab", and thus discards
the first letters "aa" and starts searching for "ab" in the last four letters
"baab" (which it also fails, for the same reason). But actually it should
backtrack to the second letter in the document and start searching for "ab" in
"baab". Or one could avoid backtracking the entity iterator by using the
Knuth-Morris-Pratt algorithm
(http://www.ics.uci.edu/~eppstein/161/960227.html), which would also give
better performance for searching long strings in long documents (but maybe not
for short search strings).


Reproducible: Always

Steps to Reproduce:
1. Open the attached file backtracking.pdf in Okular.
2. Press F3.
3. Type fast "ab" (do not pause after "a", otherwise Okular will first search
for "a").

Actual Results:  
Okular finds no match (the search text box turns reddish).

Expected Results:  
Okular should highlight the first "aab".

-- 
You are receiving this mail because:
You are the assignee for the bug.