#13961 Passwords

우선 대문자 A를 입력한 것은 blacklist를 고려한다면 소문자 a를 입력한 것과 다를게 없다.

마찬가지로 0은 'o'를 입력한 것이랑 다를게 없다.

 

그러면 이제 dp를 돌릴 건데, 트라이 상에서 dp를 돌리면 된다

아호코라식으로 알아낸 실패함수를 고려해서 상태전이를 시켜주면 된다.

이때 소문자, 대문자, 숫자가 모두 필요하므로, 각 상태를 2^3개로 비트마스킹해서 추가로 나타내주면 된다.

아호코라식을 잘 알고 있다면 (잘 모르더라도 결과만 알고 있으면) 어렵지 않게 dp를 할 수 있다.