스마트 비밀번호 검증

시간 제한1초메모리 제한2048 MB

요약

각 입력이 비밀번호와 같은지 판단합니다. 한 번의 손 위치 이동 또는 문자 하나 추가나 누락, 그리고 CAPS LOCK 오류를 허용합니다.

난이도: 보통10점 중 4점
유형: 구현, 문자열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

사람들은 여러 계정 중 하나에 비밀번호를 입력할 때 자주 실수한다. 많은 온라인 서비스가 길이가 긴 비밀번호를 요구하면서 이 문제는 더 커지고 있다. 글자 수가 많을수록 타자를 잘못 칠 가능성도 높아진다.

터치 타이핑을 하는 사람은 한 손이 올바른 홈 로우 위치에 있지 않으면 심각한 실수를 하기 쉽다. 키보드를 보지 않고 치기 때문이다. 이때 어긋난 손으로 친 글자는 모두 키 하나씩 밀린다. 예를 들어 QWERTY 키보드에서 오른손이 원래 홈 위치보다 한 키 왼쪽에 있으면 "lion"이 "kuib"으로 입력될 수 있다.

Frobozz Magic Security Company는 QWERTY 방식 키보드에서 비밀번호를 입력할 때 생기는 흔한 실수 일부를 반영한 새 비밀번호 검증 알고리즘을 도입하기로 했다. 모든 실수를 반영하지는 않는다.

그림 M.1: QWERTY 키보드

CAPS LOCK은 알파벳에만 작용하며, 그 알파벳에 대해 시프트 키의 효과를 뒤집는다. CAPS LOCK이 꺼져 있으면 시프트 키를 하나 또는 둘 다 누르지 않는 한 소문자로 입력된다. CAPS LOCK이 켜져 있으면 시프트 키를 누르지 않는 한 대문자로 입력되고, 시프트 키를 누르면 소문자가 된다. 알고리즘은 비밀번호를 입력하는 동안 CAPS LOCK 상태가 바뀌지 않는다고 가정한다.

알고리즘은 올바른 키 입력 순서에서 벗어난 부분을 찾는다. 예를 들어 올바른 비밀번호가 ALg*이면, 위 키보드에서 올바른 순서는 SHIFT-A, SHIFT-L, G, SHIFT-8이다. 사용자가 비밀번호를 입력하기 전에 실수로 CAPS LOCK을 누르고 올바른 순서대로 입력하면 alG*이 된다. 왼손 손가락을 올바른 위치보다 한 칸 오른쪽에 두고, 다른 실수 없이 어긋난 것을 모른 채 올바른 순서를 따르면 SLh*이 된다. 여기에 CAPS LOCK까지 실수로 켜져 있으면 slH*이 된다. 마지막으로 사용자는 글자를 실수로 넣거나 뺄 수도 있다. 예를 들어 ALg*은 AL*이나 ALLg*으로 잘못 입력될 수 있다.

이름	약어	설명	예시
왼쪽 면이 한 칸 밀림	LS	키보드 왼쪽에 있는 모든 문자가 오른쪽으로 한 키씩 밀린다. 왼쪽 시프트 키도 오른쪽으로 한 키 밀리지만 여전히 왼쪽 시프트 키다.	`FlatHead` $\Rightarrow$ `GlsyHrsf`
오른쪽 면이 한 칸 밀림	RS	키보드 오른쪽에 있는 모든 문자가 왼쪽으로 한 키씩 밀린다. 오른쪽 시프트 키도 왼쪽으로 한 키 밀리지만 여전히 오른쪽 시프트 키다.	`FlatHead` $\Rightarrow$ `FkatGead`
글자 하나 추가	EC	입력한 비밀번호에 글자가 하나 더 들어 있다	`Zorkmid` $\Rightarrow$ `Zorkmiid` (추가된 `i`)
글자 하나 누락	MC	입력한 비밀번호에서 글자가 하나 빠져 있다	`FCD#3` $\Rightarrow$ `FCD3` (빠진 `#`)
실수로 CAPS LOCK이 켜짐	CL	소문자는 모두 대문자로, 대문자는 모두 소문자로 나타난다	`WE do it!` $\Rightarrow$ `we DO IT!`

그림 M.2: 허용되는 오류 유형

LS, RS, EC, MC 중에서는 최대 하나의 오류만 허용된다. 다만 이들 중 어느 것이든 CL 오류와 함께 발생할 수 있다.

입력

첫 줄에는 올바른 비밀번호인 문자열 $p$ 가 주어진다 ( $2 \leq \textrm{length}(p) \leq 24$ ). 둘째 줄에는 뒤따르는 줄의 수 $n$ ( $1 \leq n \leq 1\,000$ )이 한 개의 양의 정수로 주어진다. 이어지는 $n$ 개의 줄에는 검사할 비밀번호 $t_i$ 가 한 줄에 하나씩 주어진다. 각 $t_i$ 의 길이는 $\textrm{length}(p)-1 \leq \textrm{length}(t_i) \leq \textrm{length}(p)+1$ 을 만족한다. 모든 비밀번호의 문자는 위 QWERTY 키보드 그림에 나온 문자와 소문자 알파벳만으로 이루어진다.

출력

$n$ 개의 줄을 출력한다. 각 $t_i$ 에 대해 Frobozz의 알고리즘으로 $t_i$ 가 $p$ 와 일치하면 YES, 일치하지 않으면 NO를 출력한다.

예제1

예제 1

입력

Password=`A:'
9
Password=`A:'
pASSWORD=`a:'
Psddeotf=1S:'
oASSWIRD-`al;
Password=`A:'x
pASWORD=`a:'
pASSWORD=`a:'X
Osddeitf-1SL;
Psdeotf=1S:'

예상 출력

YES
YES
YES
YES
YES
YES
YES
NO
NO