부분집합 동일성

소들은 관련 없는 문자들을 관련 있는 문자들 사이에 섞어 넣어 메시지를 해독하기 어렵게 만드는 새로운 암호 메시지 교환 방식을 시험해 보고 있다.

소들은 각각 길이가 최대 \(10^5\)이고 영어 소문자 'a'부터 'r'까지로만 이루어진 두 문자열 \(s\)와 \(t\)를 전송한다. 이 암호 메시지를 해독해 보기 위해, \(Q\)개의 쿼리(\(1 \leq Q \leq 10^5\))가 주어진다. 각 쿼리는 'a'부터 'r'까지의 영어 소문자의 부분집합을 제공한다. 각 쿼리에 대해, \(s\)와 \(t\)를 쿼리에 포함된 문자만 남기고 제한했을 때 두 문자열이 같은지 판별해야 한다.

Problem credits: Danny Mittal

채점 방식

• 테스트 케이스 2는 \(|s|, |t|, Q \le 1000\)을 만족한다.
• 테스트 케이스 3-11은 추가 제약이 없다.

Problem credits: Danny Mittal

첫째 줄에 \(s\)가 주어진다.

둘째 줄에 \(t\)가 주어진다.

셋째 줄에 \(Q\)가 주어진다.

다음 \(Q\)개의 줄에는 쿼리 문자열이 한 줄에 하나씩 주어진다. 쿼리 문자열 안에서 문자는 반복되지 않는다. 또한 모든 쿼리 문자열은 정렬된 순서로 주어지며, 같은 쿼리 문자열이 두 번 이상 등장하지 않는다.

각 쿼리에 대해, \(s\)와 \(t\)를 쿼리에 포함된 문자만 남기고 제한했을 때 두 문자열이 같으면 'Y'를, 그렇지 않으면 'N'을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > US Open > Silver