]> git.lizzy.rs Git - rust.git/commit
StrSearcher: Implement the full two way algorithm in reverse for rfind
authorUlrik Sverdrup <bluss@users.noreply.github.com>
Sun, 2 Aug 2015 17:18:44 +0000 (19:18 +0200)
committerUlrik Sverdrup <bluss@users.noreply.github.com>
Sun, 2 Aug 2015 18:09:35 +0000 (20:09 +0200)
commit7ebae85bb8eac495bbc4a463319b23404fdc63a6
treea18b49b4d0604cb25a8bae853f05e639da0fc41e
parentc5a1d8c3db171a4351712c04e6ba6a4e4636a332
StrSearcher: Implement the full two way algorithm in reverse for rfind

Fix quadratic behavior in StrSearcher in reverse search with periodic
needles.

This commit adds the missing pieces for the "short period" case in
reverse search. The short case will show up when the needle is literally
periodic, for example "abababab".

Two way uses a "critical factorization" of the needle: x = u v.

Searching matches v first, if mismatch at character k, skip k forward.
Matching u, if mismatch, skip period(x) forward.

To avoid O(mn) behavior after mismatch in u, memorize the already
matched prefix.

The short period case requires that |u| < period(x).

For the reverse search we need to compute a different critical
factorization x = u' v' where |v'| < period(x), because we are searching
for the reversed needle. A short v' also benefits the algorithm in
general.

The reverse critical factorization is computed quickly by using the same
maximal suffix algorithm, but terminating as soon as we have a location
with local period equal to period(x).

This adds extra fields crit_pos_back and memory_back for the reverse
case. The new overhead for TwoWaySearcher::new is low, and additionally
I think the "short period" case is uncommon in many applications of
string search.

The maximal_suffix methods were updated in documentation and the
algorithms updated to not use !0 and wrapping add, variable left is now
1 larger, offset 1 smaller.

Use periodicity when computing byteset: in the periodic case, just
iterate over one period instead of the whole needle.

Example before (rfind) after (twoway_rfind) benchmark shows the removal
of quadratic behavior.

needle: "ab" * 100, haystack: ("bb" + "ab" * 100) * 100

```
test periodic::rfind           ... bench:   1,926,595 ns/iter (+/- 11,390) = 10 MB/s
test periodic::twoway_rfind    ... bench:      51,740 ns/iter (+/- 66) = 386 MB/s
```
src/libcore/str/pattern.rs