에니그마

제2차 세계 대전 당시 독일의 암호 기계인 에니그마는 주어진 초기 설정에 따라 키보드로 입력된 각 글자를 다른 글자로 바꿔 놓았다. 이 치환은 상당히 복잡했지만, 한 가지 취약점이 있었다. 바로 어떤 글자도 자기 자신으로 치환되지 않는다는 점이다. 이 취약점은 전쟁 중 에니그마의 암호 해독 작업을 하던 앨런 튜링이 활용했다. 목표는 메시지에 ARMADA처럼 통신에서 흔히 쓰이는 표현이 들어 있다고 가정하여 기계의 초기 설정을 찾아내는 것이었다. 이런 표현을 크립(crib)이라고 한다.

예를 들어 암호문이 FDMLCRDMRALF라면, 가능한 기계 설정을 시험하는 작업은 단순해진다. 크립 ARMADA가 이 암호문에 들어 있다면 있을 수 있는 위치는 아래 표에서 화살표로 표시한 두 곳뿐이기 때문이다. 나머지 다섯 위치는 크립의 글자 중 하나 이상이, 아래 표에서 밑줄 친 것처럼 암호문의 대응하는 글자와 같아지므로 가능하지 않다. 에니그마는 어떤 글자도 자기 자신으로 치환하지 않으므로 이 다섯 위치는 시험 대상에서 제외할 수 있다.

이 문제에서는 암호문과 크립이 주어졌을 때, 암호문에서 크립이 있을 수 있는 위치의 수를 계산하는 프로그램을 작성해야 한다.

첫째 줄에는 암호문이 주어진다. 암호문은 길이가 1 이상 104 이하인 글자열이다. 둘째 줄에는 크립이 주어진다. 크립은 길이가 1 이상이고 암호문의 길이 이하인 글자열이다. 암호문과 크립에는 악센트가 없는 알파벳 대문자 26개만 나타난다.

암호문에서 크립이 있을 수 있는 위치의 수를 나타내는 정수를 한 줄에 출력한다.