패턴으로 검색하기

패턴 $P$와 텍스트 $T$가 주어진다. 둘 다 라틴 문자(소문자와 대문자)로만 이루어져 있다. 패턴에는 추가로 ?, [, ], {, } 문자가 들어갈 수 있다. $P$가 $T$에 나타나는 모든 위치를 찾아야 한다.

패턴 $P$의 각 위치는 다음 중 하나이다.

• 라틴 문자(a–z, A–Z): 정확히 그 문자와 일치한다.
• 문자 ?: 임의의 문자 하나와 일치한다.
• 그룹 [...]: 이 위치에 올 수 있는 문자들의 집합을 나열한다.
• 그룹 {...}: 이 위치에 올 수 없는 문자들의 집합을 나열한다(그 외의 문자는 모두 허용된다).

그룹 안에서 문자는 [asssa]나 {kLLf}처럼 중복될 수 있다. 대소문자는 구분한다.

예를 들어 패턴이 A?[bcCc]{De}라면, 일치의 첫 번째 문자는 반드시 A, 두 번째는 임의의 라틴 문자, 세 번째는 b, c, C 중 하나, 네 번째는 D와 e를 제외한 임의의 라틴 문자여야 한다.

첫 줄에 테스트 케이스의 수 $n$이 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 패턴 $P$(문자 $100$개 이하, 위치 $60$개 이하)가, 둘째 줄에는 텍스트 $T$(문자 $10^6$개 이하)가 주어진다.

각 테스트 케이스마다, 패턴이 일치하는 텍스트의 모든 위치를 오름차순으로 한 줄에 출력한다($T$의 첫 문자의 위치는 $1$이다). 위치 사이에는 공백 하나만 넣고, 줄의 처음이나 끝에 불필요한 공백을 두지 않는다. $P$가 $T$에 나타나지 않으면 대신 no match를 출력한다.