문제
알파벳 소문자로 이루어진 문자열 $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$와 매칭되는지, 매칭된다면 유일한지 여부를 출력한다.
출력
각 쿼리에 대한 답을 $Q$개의 줄에 걸쳐 순서대로 출력한다.
그중 $i$번째 줄에는 각 $T_{i}$에 대해서 $S$와 매칭되지 않는 경우 0, 매칭되고 유일한 경우 1, 그 외의 경우 2를 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MDg5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiV2lsZGNhcmQgYW5kIFF1ZXJ5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFMkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MCBcdWJjMGYgJnF1b3Q7KiZxdW90O1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0ICRUJFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMgJFMkXHVjNjQwIDxzdHJvbmc+XHViOWU0XHVjZTZkPFwvc3Ryb25nPlx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kVCRcdWM3NTggXHVhYzAxICZxdW90OyomcXVvdDtcdWI0ZTRcdWM3NDQgXHVhYzAxXHVhYzAxIFx1YWUzOFx1Yzc3NFx1YWMwMCAkMCQgXHVjNzc0XHVjMGMxXHVjNzc4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMzAwXHVjY2I0XHVkNTg4XHVjNzQ0IFx1YjU0YyAkUyRcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCAmcXVvdDthKmImcXVvdDtcdWIyOTQgJnF1b3Q7YWImcXVvdDssICZxdW90O2FjYiZxdW90OywgJnF1b3Q7YWFiYiZxdW90OyBcdWI0ZjFcdWFjZmMgPHN0cm9uZz5cdWI5ZTRcdWNlNmQ8XC9zdHJvbmc+XHViNDE4XHVjOWMwXHViOWNjICZxdW90O2FiYyZxdW90O1x1YzY0MFx1YjI5NCA8c3Ryb25nPlx1YjllNFx1Y2U2ZDxcL3N0cm9uZz5cdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTRcdWJhNzQgPHN0cm9uZz5cdWI5ZTRcdWNlNmQ8XC9zdHJvbmc+XHVjNzc0IDxzdHJvbmc+XHVjNzIwXHVjNzdjPFwvc3Ryb25nPlx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kVCRcdWM3NTggXHVhYzAxICZxdW90OyomcXVvdDtcdWI5N2MgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjMwMFx1Y2NiNFx1ZDU1OFx1YzVlYyAkUyRcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCAmcXVvdDthKmIqYyZxdW90O1x1YjI5NCAmcXVvdDthYmMmcXVvdDssICZxdW90O2F4YnhjJnF1b3Q7XHVjNjQwXHVjNzU4IDxzdHJvbmc+XHViOWU0XHVjZTZkPFwvc3Ryb25nPlx1Yzc0MCA8c3Ryb25nPlx1YzcyMFx1Yzc3YzxcL3N0cm9uZz5cdWQ1NThcdWM5YzBcdWI5Y2MsICZxdW90O2FiYmMmcXVvdDtcdWM2NDBcdWM3NTggPHN0cm9uZz5cdWI5ZTRcdWNlNmQ8XC9zdHJvbmc+XHVjNzQwIDxzdHJvbmc+XHVjNzIwXHVjNzdjPFwvc3Ryb25nPlx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggJnF1b3Q7KiZxdW90O1x1Yjk3YyAmcXVvdDtiJnF1b3Q7LCBcdWI0NTAgXHViYzg4XHVjOWY4ICZxdW90OyomcXVvdDtcdWI5N2MgXHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YjRcdWIzYzQgXHViNDE4XHVhY2UwLCBcdWNjYWIgXHViYzg4XHVjOWY4ICZxdW90OyomcXVvdDtcdWI5N2MgXHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNCwgXHViNDUwIFx1YmM4OFx1YzlmOCAmcXVvdDsqJnF1b3Q7XHViOTdjICZxdW90O2ImcXVvdDtcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWI0XHViM2M0IFx1YjQxOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiRTJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1YjJlNFx1Yzc0YyBcdWNmZmNcdWI5YWNcdWM1ZDAgXHViMmY1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViYjM4XHVjNzkwXHVjNWY0ICRUJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgJFQkXHVhYzAwICRTJFx1YzY0MCA8c3Ryb25nPlx1YjllNFx1Y2U2ZDxcL3N0cm9uZz5cdWI0MThcdWIyOTRcdWM5YzAsIDxzdHJvbmc+XHViOWU0XHVjZTZkPFwvc3Ryb25nPlx1YjQxY1x1YjJlNFx1YmE3NCA8c3Ryb25nPlx1YzcyMFx1Yzc3YzxcL3N0cm9uZz5cdWQ1NWNcdWM5YzAgXHVjNWVjXHViZDgwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFMkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxXFxsZSB8U3xcXGxlIDMwMFxcLCAwMDAkKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWMyMTggJFEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxXFxsZSBRXFxsZSAzMDBcXCwgMDAwJCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWFkZjhcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFRfe2l9JFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICRUX3tpfSRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MCBcdWJjMGYgJnF1b3Q7KiZxdW90O1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjZmZjXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU3NCAkVF97aX0kXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NDAgJDMwMFxcLCAwMDAkIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjZmZjXHViOWFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDQgJFEkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHVjOTExICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxICRUX3tpfSRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjICRTJFx1YzY0MCA8c3Ryb25nPlx1YjllNFx1Y2U2ZDxcL3N0cm9uZz5cdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MDxcL2NvZGU+PFwvc3Bhbj4sIDxzdHJvbmc+XHViOWU0XHVjZTZkPFwvc3Ryb25nPlx1YjQxOFx1YWNlMCA8c3Ryb25nPlx1YzcyMFx1Yzc3YzxcL3N0cm9uZz5cdWQ1NWMgXHVhY2JkXHVjNmIwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4xPFwvY29kZT48XC9zcGFuPiwgXHVhZGY4IFx1YzY3OFx1Yzc1OCBcdWFjYmRcdWM2YjAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjI8XC9jb2RlPjxcL3NwYW4+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNDA4OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldpbGRjYXJkIGFuZCBRdWVyeSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHN0cmluZyAkUyQgY29uc2lzdGluZyBvZiBsb3dlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC48XC9wPlxyXG5cclxuPHA+QSBzdHJpbmcgJFQkIGNvbnNpc3Rpbmcgb2YgRW5nbGlzaCBsb3dlcmNhc2UgbGV0dGVycyBhbmQgJnF1b3Q7KiZxdW90OyBpcyBjb25zaWRlcmVkIHRvIDxzdHJvbmc+bWF0Y2g8XC9zdHJvbmc+ICRTJCB3aGVuIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uIGlzIHNhdGlzZmllZC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kUyQgY2FuIGJlIG1hZGUgZnJvbSAkVCQgYnkgcmVwbGFjaW5nIGVhY2ggJnF1b3Q7KiZxdW90OyB3aXRoIGFuIGFyYml0cmFyeSBzdHJpbmcgb2YgbGVuZ3RoICQwJCBvciBncmVhdGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCAmcXVvdDthKmImcXVvdDsgPHN0cm9uZz5tYXRjaDxcL3N0cm9uZz5lcyAmcXVvdDthYiZxdW90OywgJnF1b3Q7YWNiJnF1b3Q7LCBhbmQgJnF1b3Q7YWFiYiZxdW90OyBidXQgZG9lcyBub3QgPHN0cm9uZz5tYXRjaDxcL3N0cm9uZz4gJnF1b3Q7YWJjJnF1b3Q7LjxcL3A+XHJcblxyXG48cD5BIDxzdHJvbmc+bWF0Y2g8XC9zdHJvbmc+IGlzIGNvbnNpZGVyZWQgPHN0cm9uZz51bmlxdWU8XC9zdHJvbmc+IGlmIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uIGlzIHNhdGlzZmllZC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGVyZSBpcyBvbmx5IG9uZSBwb3NzaWJsZSB3YXkgb2YgcmVwbGFjaW5nIGVhY2ggJnF1b3Q7KiZxdW90OyBpbiAkVCQgdG8gbWFrZSAkUyQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsICZxdW90O2EqYipjJnF1b3Q7IDxzdHJvbmc+dW5pcXVlPFwvc3Ryb25nPmx5IDxzdHJvbmc+bWF0Y2g8XC9zdHJvbmc+ZXMgJnF1b3Q7YWJjJnF1b3Q7IGFuZCAmcXVvdDtheGJ4YyZxdW90OyBidXQgZG9lcyBub3QgPHN0cm9uZz51bmlxdWU8XC9zdHJvbmc+bHkgPHN0cm9uZz5tYXRjaDxcL3N0cm9uZz4gJnF1b3Q7YWJiYyZxdW90Oy4gVGhpcyBpcyBiZWNhdXNlIHlvdSBjYW4gcmVwbGFjZSB0aGUgZmlyc3QgJnF1b3Q7KiZxdW90OyB3aXRoICZxdW90O2ImcXVvdDsgYW5kIHRoZSBzZWNvbmQgJnF1b3Q7KiZxdW90OyB3aXRoIGFuIGVtcHR5IHN0cmluZywgb3IgYWx0ZXJuYXRpdmVseSwgcmVwbGFjZSB0aGUgZmlyc3QgJnF1b3Q7KiZxdW90OyB3aXRoIGFuIGVtcHR5IHN0cmluZyBhbmQgdGhlIHNlY29uZCAmcXVvdDsqJnF1b3Q7IHdpdGggJnF1b3Q7YiZxdW90Oy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gJFMkLCB3cml0ZSBhIHByb2dyYW0gd2hpY2ggYW5zd2VycyB0aGUgZm9sbG93aW5nIHF1ZXJpZXMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+R2l2ZW4gYSBzdHJpbmcgJFQkLCBkZXRlcm1pbmUgd2hldGhlciAkVCQgYW5kICRTJCA8c3Ryb25nPm1hdGNoPFwvc3Ryb25nPiBhbmQgaWYgdGhleSBkbywgd2hldGhlciB0aGUgPHN0cm9uZz5tYXRjaDxcL3N0cm9uZz4gaXMgPHN0cm9uZz51bmlxdWU8XC9zdHJvbmc+LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyAkUyQsIGEgc3RyaW5nIGNvbnNpc3Rpbmcgb2YgbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuICgkMVxcbGUgfFN8XFxsZSAzMDBcXCwgMDAwJCk8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICRRJCwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBxdWVyaWVzLiAoJDFcXGxlIFFcXGxlIDMwMFxcLCAwMDAkKTxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJFEkIGxpbmVzIGNvbnRhaW5zIGEgc3RyaW5nICRUX3tpfSQuICRUX3tpfSQgY29uc2lzdHMgb2YgRW5nbGlzaCBsb3dlcmNhc2UgbGV0dGVycyBhbmQgJnF1b3Q7KiZxdW90Oy48XC9wPlxyXG5cclxuPHA+VGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiAkVF97aX0kIG92ZXIgYWxsIHF1ZXJpZXMgZG9lcyBub3QgZXhjZWVkICQzMDBcXCwgMDAwJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCAkVF97aX0kLCBwcmludCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MDxcL2NvZGU+PFwvc3Bhbj4gaWYgaXQgZG9lcyBub3QgPHN0cm9uZz5tYXRjaDxcL3N0cm9uZz4gJFMkLCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MTxcL2NvZGU+PFwvc3Bhbj4gaWYgdGhlIDxzdHJvbmc+bWF0Y2g8XC9zdHJvbmc+IGlzIDxzdHJvbmc+dW5pcXVlPFwvc3Ryb25nPiwgYW5kIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4yPFwvY29kZT48XC9zcGFuPiBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==