34089번 - Wildcard and Query 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 220 | 31 | 18 | 9.945% |
문제
알파벳 소문자로 이루어진 문자열 $S$가 주어진다.
알파벳 소문자 및 "*"로 이루어진 문자열 $T$는 다음 조건을 만족할 때 $S$와 매칭된다.
- $T$의 각 "*"들을 각각 길이가 $0$ 이상인 임의의 문자열로 대체했을 때 $S$를 만들 수 있다.
예를 들어 "a*b"는 "ab", "acb", "aabb" 등과 매칭되지만 "abc"와는 매칭되지 않는다.
만약 다음 조건을 만족한다면 매칭이 유일하다.
- $T$의 각 "*"를 문자열로 대체하여 $S$를 만드는 방법이 유일하다.
예를 들어 "a*b*c"는 "abc", "axbxc"와의 매칭은 유일하지만, "abbc"와의 매칭은 유일하지 않다. 첫 번째 "*"를 "b", 두 번째 "*"를 빈 문자열로 바꾸어도 되고, 첫 번째 "*"를 빈 문자열, 두 번째 "*"를 "b"로 바꾸어도 되기 때문이다.
$S$가 주어질 때 다음 쿼리에 답하는 프로그램을 작성하여라.
- 문자열 $T$가 주어지면 $T$가 $S$와 매칭되는지, 매칭된다면 유일한지 여부를 출력한다.
입력
첫째 줄에 알파벳 소문자로 이루어진 문자열 $S$가 주어진다. ($1\le |S|\le 300\, 000$)
둘째 줄에 쿼리의 수 $Q$가 주어진다. ($1\le Q\le 300\, 000$)
이후 $Q$개의 줄에 걸쳐, 그중 $i$번째 줄에는 문자열 $T_{i}$가 주어진다. $T_{i}$는 알파벳 소문자 및 "*"로 이루어져 있다.
모든 쿼리에 대해 $T_{i}$들의 길이의 합은 $300\, 000$ 이하이다.
출력
각 쿼리에 대한 답을 $Q$개의 줄에 걸쳐 순서대로 출력한다.
그중 $i$번째 줄에는 각 $T_{i}$에 대해서 $S$와 매칭되지 않는 경우 0, 매칭되고 유일한 경우 1, 그 외의 경우 2를 출력한다.
예제 입력 1
axbbc 3 abc a*c a*b*c
예제 출력 1
0 1 2
출처
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2025 D번
- 문제를 만든 사람: cki86201
- 문제를 검수한 사람: evenharder, functionx, kipa00, leo020630, ncy09, queued_q, qwerasdfzxcl, seonah
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호