On a system I used several years ago users were forced to change passwords regularly and the new password was checked for similarity to previous passwords.
I can see that previous passwords could be easily checked for equality with the new password by comparing the hash to a list of expired hashes and I suppose it's possible to make modifications to the password before hashing it to see if it's similar in that way.
For example. If the old password was "my secret" and the user tried to set the new password to "my secret2" there might a rule to remove numbers and hash that to check for similarity. That approach seems quite limited however.
Is there a way of checking new passwords for similarity that uses secure storage of the password and isn't hugely computationally expensive?