search

lewang / flx

Fuzzy matching for Emacs ... a la Sublime Text.
GNU General Public License v3.0
518 stars 37 forks source link

corner cases confuse matcher #34

Closed lewang closed 8 years ago

lewang commented 11 years ago

Matching "lllllll" against "~/foo/bar/blah.elllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll" takes a long time.

PythonNut commented 9 years ago

I've heard of this before. Could this be because .*l.*l.*l.*l.*l.*l.*l.* matches lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll 8^60 different ways?

jeancroy commented 8 years ago

A dynamic programming table will solve this in o(m*n) step.

This is because amongs the 8^60 or so permutation, there are a lot of subproblem that can be calculated once then re-used.