I wrote one very similar to what you are describing. They can be done as a regular expression, and when complete (at least for myself) it was a very rewarding accomplishment.
To accomplish this you are going to need to use a regex feature called lookaheads. See the information on the regular-expression.info site for all the gory details.
The second thing you will need is a real time regular expression tester to help you prototype your regex. I suggestion you check out Rubular. Create several passwords that should work, and some that shouldn't work and start from there as your starting point.
Edit:
To elaborate on my above comment. Not every one of your requirements can or should be solved via a regex. Namely, the requirements you listed as:
- Must not contain any sequence of 3 or more characters in common with the username
- Must not repeat any of the previous 1 passwords
- Must be changed if the password is believed to be compromised in any way
Should probably be handled separately from the main password validation regex, as these are highly contextual. The "sequence of 3 or more characters in common with the username" can probably be handled on the client side. However, the other two items are probably best left handled on the server side.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…