시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB63917311726.471%

문제

이모티콘은 채팅과 이메일에서 단어로 표현할 수 없는 감정을 나타내기 위해 종종 쓰인다. 이는 다양한 면에서 장점이 있지만, 많은 사람들은 이모티콘을 매우 짜증난다고 여기며, 없애고 싶어한다.

세종이가 딱 그렇다. 세종이는 이모티콘을 너무 싫어한 나머지, 전세계의 이메일에서 이모티콘을 없애버릴 계획을 세웠다. 당신은 세종이와 계획을 함께 준비하고 있어서, 세종이를 도와줄 특별한 프로그램을 제작하려고 한다.

프로그램은 제거할 이모티콘의 리스트를 먼저 받는다. 각 이모티콘은 공백(whitespace)을 포함하지 않은 문자열이다. 또한 몇몇 텍스트도 함께 받는다. 이때 프로그램이 해야 할 일은 텍스트의 몇몇 글자를 공백으로 바꿔서 원래 존재하던 모든 이모티콘을 없애버리는 것이다. 원래 텍스트의 한 줄에만 걸쳐 나타나며, 사이에 다른 공백이나 문자열이 끼어 있지 않은 이모티콘만을 이모티콘이라고 할 것이다.

세종이의 계획을 최대한 들통나지 않게 하기 위해, 당신은 공백으로 대체할 문자의 개수를 최소한으로 해야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 여러 줄로 이루어져 있다. 첫 번째 줄은 이모티콘의 개수 N과 텍스트 줄 수 M이 주어지며, 다음 N개의 줄에는 15글자 이하의 비어 있지 않은 문자열인 각 이모티콘이 주어진다. 그 다음 M개의 줄에는 이모티콘을 지울 텍스트들이 주어지며 80글자 이하이다. 1 ≤ N, M ≤ 100 이라 가정해도 좋다.

이모티콘은 영어 대소문자, 숫자, 그리고 특수문자 “!?.,:;-_'#\$%&/=*+(){}[]”(큰따옴표는 포함되지 않음)로만 구성될 수 있다. 텍스트는 여기에 추가로 공백문자까지 포함할 수 있다.

입력의 끝에는 N = M = 0이 주어진다.

출력

각 테스트 케이스에 걸쳐, 한 줄에 하나씩 공백으로 대체해야 할 문자의 최소 개수를 출력한다.

예제 입력 1

4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0

예제 출력 1

11
8
W3sicHJvYmxlbV9pZCI6IjU3MzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJFbW90aWNvbnMgOi0pIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDAgXHVjYzQ0XHVkMzA1XHVhY2ZjIFx1Yzc3NFx1YmE1NFx1Yzc3Y1x1YzVkMFx1YzExYyBcdWIyZThcdWM1YjRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhYzEwXHVjODE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODg1XHVjODg1IFx1YzRmMFx1Yzc3OFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWJhNzRcdWM1ZDBcdWMxMWMgXHVjN2E1XHVjODEwXHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgXHViOWNlXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzlkY1x1Yzk5ZFx1YjA5Y1x1YjJlNFx1YWNlMCBcdWM1ZWNcdWFlMzBcdWJhNzAsIFx1YzVjNlx1YzU2MFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWI1MzEgXHVhZGY4XHViODA3XHViMmU0LiBcdWMxMzhcdWM4ODVcdWM3NzRcdWIyOTQgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzQ0IFx1YjEwOFx1YmIzNCZuYnNwO1x1YzJlYlx1YzViNFx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAsIFx1YzgwNFx1YzEzOFx1YWNjNFx1Yzc1OCBcdWM3NzRcdWJhNTRcdWM3N2NcdWM1ZDBcdWMxMWMgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmM4NFx1YjliNCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAmbmJzcDtcdWMxMzhcdWM4ODVcdWM3NzRcdWM2NDAgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1ZDU2OFx1YWVkOCBcdWM5MDBcdWJlNDRcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWMxMzhcdWM4ODVcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOTA0IFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjODFjXHVjNzkxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YzgxY1x1YWM3MFx1ZDU2MCBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NTggXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YmEzY1x1YzgwMCBcdWJjMWJcdWIyOTRcdWIyZTQuIFx1YWMwMSBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDAgXHVhY2Y1XHViYzMxKHdoaXRlc3BhY2UpXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHViYTg3XHViYTg3IFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YjNjNCBcdWQ1NjhcdWFlZDggXHViYzFiXHViMjk0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1Yzc1OCBcdWJhODdcdWJhODcgXHVhZTAwXHVjNzkwXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmZDRcdWMxMWMgXHVjNmQwXHViNzk4IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjM1OCBcdWJhYThcdWI0ZTAgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmM4NFx1YjlhY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzZkMFx1Yjc5OCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM3NTggXHVkNTVjIFx1YzkwNFx1YzVkMFx1YjljYyBcdWFjNzhcdWNjZDAgXHViMDk4XHVkMGMwXHViMDk4XHViYTcwLCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViMmU0XHViOTc4IFx1YWNmNVx1YmMzMVx1Yzc3NFx1YjA5OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViMDdjXHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHViOWNjXHVjNzQ0IFx1Yzc3NFx1YmFhOFx1ZDJmMFx1Y2Y1OFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzhcdWM4ODVcdWM3NzRcdWM3NTggXHVhY2M0XHVkNjhkXHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI0ZTRcdWQxYjVcdWIwOThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViMzAwXHVjY2I0XHVkNTYwIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzNjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzVlY1x1YjdlYyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NDAgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1ZDE0ZFx1YzJhNFx1ZDJiOCBcdWM5MDQgXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMTVcdWFlMDBcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmU0NFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3OCBcdWFjMDEgXHVjNzc0XHViYWE4XHVkMmYwXHVjZjU4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzRcdWJhYThcdWQyZjBcdWNmNThcdWM3NDQgXHVjOWMwXHVjNmI4IFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgODBcdWFlMDBcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiZuYnNwOzEgJmxlOyBOLCBNICZsZTsgMTAwJm5ic3A7XHVjNzc0XHViNzdjIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YmFhOFx1ZDJmMFx1Y2Y1OFx1Yzc0MCBcdWM2MDFcdWM1YjQgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwLCBcdWMyMmJcdWM3OTAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQyYjlcdWMyMThcdWJiMzhcdWM3OTAmbmJzcDsmbGRxdW87IT8uLDo7LV8mIzM5OyNcXCQlJmFtcDtcLz0qKygpe31bXSZyZHF1bzsoXHVkMDcwXHViNTMwXHVjNjM0XHVkNDVjXHViMjk0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NGMpXHViODVjXHViOWNjIFx1YWQ2Y1x1YzEzMVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQxNGRcdWMyYTRcdWQyYjhcdWIyOTQgXHVjNWVjXHVhZTMwXHVjNWQwIFx1Y2Q5NFx1YWMwMFx1Yjg1YyBcdWFjZjVcdWJjMzFcdWJiMzhcdWM3OTBcdWFlNGNcdWM5YzAgXHVkM2VjXHVkNTY4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM1ZDBcdWIyOTQgTiA9IE0gPSAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWFjNzhcdWNjZDAsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWIzMDBcdWNjYjRcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YmIzOFx1Yzc5MFx1Yzc1OCZuYnNwO1x1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjU3MzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFbW90aWNvbnMgOi0pIiwiZGVzY3JpcHRpb24iOiI8cD5FbW90aWNvbnMgYXJlIHVzZWQgaW4gY2hhdCBhbmQgZS1tYWlsIGNvbnZlcnNhdGlvbnMgdG8gdHJ5IHRvIGV4cHJlc3MgdGhlIGVtb3Rpb25zIHRoYXQgcHJpbnRlZCB3b3JkcyBjYW5ub3QuIFRoaXMgbWF5IHNlZW0gbGlrZSBhIG5pY2UgZmVhdHVyZSBmb3IgbWFueSwgYnV0IGEgbG90IG9mIHBlb3BsZSBmaW5kIGl0IHJlYWxseSBhbm5veWluZyBhbmQgd2FudHMgdG8gZ2V0IHJpZCBvZiBlbW90aWNvbnMuPFwvcD5cclxuXHJcbjxwPkdlb3JnZSBpcyBvbmUgb2YgdGhvc2UgcGVvcGxlLiBIZSBoYXRlcyBlbW90aWNvbnMgc28gYmFkLCB0aGF0IGhlIGlzIHByZXBhcmluZyBhIHBsYW4gdG8gcmVtb3ZlIGFsbCBlbW90aWNvbnMgZnJvbSBhbGwgZS1tYWlscyBpbiB0aGUgd29ybGQuIFNpbmNlIHlvdSBzaGFyZSBoaXMgdmlzaW9uYXJ5IHBsYW5zLCB5b3UgYXJlIHByZXBhcmluZyBhIHNwZWNpYWwgcHJvZ3JhbSB0byBoZWxwIGhpbS48XC9wPlxyXG5cclxuPHA+WW91ciBwcm9ncmFtIHdpbGwgcmVjZWl2ZSB0aGUgbGlzdCBvZiBlbW90aWNvbnMgdG8gcHJvc2NyaWJlLiBFYWNoIGVtb3RpY29uIHdpbGwgYmUgYSBzdHJpbmcgb2YgY2hhcmFjdGVycyBub3QgaW5jbHVkaW5nIGFueSB3aGl0ZXNwYWNlLiBZb3Ugd2lsbCBhbHNvIHJlY2VpdmUgc2V2ZXJhbCBsaW5lcyBvZiB0ZXh0LiBXaGF0IHlvdSBuZWVkIHRvIGRvIGlzIGNoYW5nZSBzb21lIGNoYXJhY3RlcnMgb2YgdGhlIHRleHQgaW50byBzcGFjZXMgdG8gZW5zdXJlIG5vIGVtb3RpY29uIGlzIGxlZnQgb24gdGhlIHRleHQuIEZvciBhbiBlbW90aWNvbiB0byBiZSBjb25zaWRlcmVkIHRvIGFwcGVhciBpbiB0aGUgdGV4dCBpdCBoYXMgdG8gYXBwZWFyIGluIGEgc2luZ2xlIGxpbmUgYW5kIGJlIG1hZGUgb2YgY29uc2VjdXRpdmUgY2hhcmFjdGVycy48XC9wPlxyXG5cclxuPHA+VG8gaGVscCBHZW9yZ2UmcnNxdW87cyBwbGFuIHJlbWFpbiBzZWNyZXQgYXMgbG9uZyBhcyBwb3NzaWJsZSwgeW91IG5lZWQgdG8gZG8geW91ciBqb2Igd2l0aCB0aGUgbWluaW11bSBwb3NzaWJsZSBhbW91bnQgb2YgY2hhcmFjdGVyIGNoYW5nZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHNldmVyYWwgbGluZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlOiBOLCB0aGUgbnVtYmVyIG9mIGVtb3RpY29ucyB0byBwcm9zY3JpYmUsIGFuZCBNLCB0aGUgbnVtYmVyIG9mIGxpbmVzIHRoZSB0ZXh0IGhhcy4gVGhlIG5leHQgTiBsaW5lcyBjb250YWluIG9uZSBlbW90aWNvbiBlYWNoLCBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgYXQgbW9zdCAxNSBjaGFyYWN0ZXJzLiBFYWNoIG9mIHRoZSBsYXN0IE0gbGluZXMgb2YgdGhlIHRlc3QgY2FzZSBjb250YWlucyBhIGxpbmUgb2YgdGV4dCBvZiBhdCBtb3N0IDgwIGNoYXJhY3RlcnMuIFlvdSBjYW4gYXNzdW1lIDEgJmxlOyBOLCBNICZsZTsgMTAwLjxcL3A+XHJcblxyXG48cD5WYWxpZCBpbnB1dCBjaGFyYWN0ZXJzIGZvciBlbW90aWNvbnMgYXJlIHVwcGVyY2FzZSBhbmQgbG93ZXJjYXNlIGxldHRlcnMsIGRpZ2l0cyBhbmQgdGhlIHN5bWJvbHMgJmxkcXVvOyE/Liw6Oy1fJiMzOTsjXFwkJSZhbXA7XC89KisoKXt9W10mcmRxdW87IChxdW90ZXMgZm9yIGNsYXJpdHkpLiBFYWNoIGxpbmUgb2YgdGhlIHRleHQgbWF5IGNvbnRhaW4gdGhlIHNhbWUgY2hhcmFjdGVycyB3aXRoIHRoZSBhZGRpdGlvbiBvZiB0aGUgc3BhY2UgY2hhcmFjdGVyLjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSBOID0gTSA9IDAuPFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBtdXN0IGJlIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBleGFjdGx5IG9uZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciB0aGF0IGluZGljYXRlcyB0aGUgbWluaW11bSBudW1iZXIgb2YgY2hhbmdlcyB5b3UgbmVlZCB0byBtYWtlIHRvIHRoZSBlbnRpcmUgdGV4dCB0byBlbnN1cmUgbm8gZW1vdGljb24gb24gdGhlIGxpc3QgYXBwZWFycyBpbiBpdC48XC9wPlxyXG5cclxuPHA+VGhlIG91dHB1dCBtdXN0IGJlIHdyaXR0ZW4gdG8gc3RhbmRhcmQgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Latin America > South America Regional Contests 2007 E번

  • 문제를 번역한 사람: kks227