You could go the other way, and check likely candidates from the new password - e.g. if user enters "hunter2", you check hunter and hunter0 and hunter1 and hunter3 and hunt3r2.