search

trichards57 / zxcvbn-cs

C#/.NET port of Dan Wheeler/DropBox's Zxcvbn JS password strength estimation library
MIT License
59 stars 18 forks source link

Bad performance in DictionaryMatcher #34

Open Abrynos opened 3 years ago

Abrynos commented 3 years ago

The current logic in DictionaryMatcher.cs is quite slow. I'd like to propose changing it to use a proper algorithm searching for a finite set of patterns. In particular I'd like to suggest the Commentz-Walter, which is the multi-pattern equivalent of the Boyer-Moore and thus extremely fast.

Thank you for considering this enhancement. If you want: I am willing to send a merge request implementing it.

winnerlein commented 1 year ago

A simpler improvement which limits j - i to the longest word in the dictionary should already improve performance for long passwords (going from O(n^2) to O(n), albeit with a dictionary dependent constant).