상범이의 은밀한 메시지
면접 대비시간 제한1초메모리 제한128 MB
비줴네르 방식으로 암호화된 문자열과 평문의 일부 연속 부분이 주어졌을 때 반복 키를 추론해 원문 전체를 복호화합니다.
문제
상범이는 민균이의 계정 비밀번호를 알아냈고, 태욱이에게 그 비밀번호를 메시지로 보내려 한다. 민균이가 메시지를 훔쳐보더라도 내용을 알 수 없도록, 상범이는 additional key 암호화 방식으로 메시지를 암호화한다. 메시지와 키는 모두 소문자 알파벳 문자열이다. 암호화는 다음 순서로 진행된다.
- 키를 메시지와 길이가 같아질 때까지 반복한다.
- 각 문자를
a = 0,b = 1, ...,z = 25로 바꾼다. - 같은 위치의 메시지 값과 키 값을 더한다. 합이 26 이상이면 26을 빼서 0 이상 25 이하로 만든다.
- 얻은 값을 다시 문자로 바꾸어 암호문을 만든다.
메시지가 sutraujutro이고 키가 abz라면 암호문은 svsrbtjvsrp가 된다.
s u t r a u j u t r o 18 20 19 17 0 20 9 20 19 17 14
+ a b z a b z a b z a b + 0 1 25 0 1 25 0 1 25 0 1
-------------------------------------------------------------------------
s v s r b t j v s r p 18 21 18 17 1 19 9 21 18 17 15
민균이는 암호화 방식을 알고 있으며, 암호화되기 전 메시지의 연속한 일부를 보았다. 다만 그 일부가 원래 메시지의 어느 위치에 있는지는 모른다. 본 부분의 길이는 항상 키 길이의 두 배 이상이다.
암호문과 암호화되기 전 메시지의 일부가 주어질 때, 원래 메시지를 구하라.
입력
첫째 줄에 암호문이 주어진다. 암호문의 길이는 1000 이하이며 소문자 알파벳으로만 이루어져 있다.
둘째 줄에 암호화되기 전 메시지의 연속한 일부가 주어진다. 이 문자열의 길이는 100 이하이며 소문자 알파벳으로만 이루어져 있다.
출력
암호화되기 전의 원래 메시지를 출력한다.