시저 암호
시간 제한2초메모리 제한256 MB
임의의 알파벳 순서와 평문 단어, 암호문이 주어질 때 복호화한 문자열에서 단어가 정확히 한 번 나타나는 모든 시프트 값을 문자열 매칭으로 찾는 문제입니다.
문제
시저 암호는 정해진 알파벳 순서에서 각 문자를 일정한 칸수만큼 뒤에 있는 문자로 바꾸는 대치 암호이다. 알파벳의 끝을 지나면 다시 처음으로 돌아간다. 예를 들어 일반적인 대문자 알파벳에서 시프트 값이 3이면 A는 D로, B는 E로, X는 A로 바뀐다. 이때 이동한 칸수를 시프트 값이라고 한다.
알파벳 순서 A, 원문 W, 암호문 S가 주어진다. 시프트 값 x로 S를 복호화했을 때 W가 복호문 안에 정확히 한 번 나타나면 x는 가능한 값이다. 0 <= x < |A| 범위에서 가능한 모든 시프트 값을 구하라.
입력
첫 줄에 테스트 케이스의 수 N이 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 알파벳 순서 A, 원문 W, 암호문 S가 이 순서대로 주어진다.
A는 알파벳 소문자, 알파벳 대문자, 숫자만 포함한다. A의 순서는 사전순이 아닐 수 있으며, A에 포함된 문자는 모두 서로 다르다.
입력 범위는 3 <= |A| <= 62, 1 <= |W| <= 50,000, 3 <= |S| <= 500,000 이다.
출력
각 테스트 케이스마다 한 줄을 출력한다.
조건을 만족하는 시프트 값이 없으면 no solution을 출력한다.
조건을 만족하는 시프트 값이 하나뿐이면 unique: x를 출력한다. 여기서 x는 그 시프트 값이다.
조건을 만족하는 시프트 값이 여러 개이면 ambiguous: 를 출력한 뒤, 가능한 시프트 값을 오름차순으로 공백으로 구분해 출력한다.