시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 401 51 28 17.610%

문제

상근이네 집 앞의 아스키 거리는 알파벳 소문자가 적혀 있는 타일 N개로 이루어져 있다. 정부는 알 수 없는 이유 때문에 거리의 타일을 자주 바꾼다. 하지만, 글자가 적혀있는 타일은 공급이 수요를 따라갈 수 없기 때문에 정부는 M종류의 묶음 타일만 사용할 수 있다.

i번째 묶음 타일은 Li개의 글자로 이루어져 있다. 묶음 타일은 회전하거나 조각으로 나눌 수 없다. 또, 거리와 연속해서 글자가 모두 일치하는 경우에만 그 묶음을 사용해서 타일을 교체할 수 있다. 타일은 겹쳐도 상관없고, 한 묶음을 여러 번 사용해도 된다.

현재 거리에 쓰여 있는 타일과 묶음 타일의 정보가 주어졌을 때, 그 어떤 타일로도 바꿀 수 없는 칸의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 거리의 길이 N이 주어진다. 다음 줄에는 거리에 원래 적혀져있는 알파벳이 주어진다. 셋째 줄에는 묶음 타일의 종류의 개수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적혀져있는 알파벳이 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ M ≤ 5000, 1 ≤ 각 묶음 타일의 길이 ≤ 5000)

출력

첫째 줄에 그 어떤 묶음 타일로도 바꿀 수 없는 타일의 개수를 출력한다.

예제 입력 1

6
abcbab
2
cb
cbab

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjI4MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWMyYTRcdWQwYTQgXHVhYzcwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjOWQxIFx1YzU1ZVx1Yzc1OCBcdWM1NDRcdWMyYTRcdWQwYTQgXHVhYzcwXHViOWFjXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWQwYzBcdWM3N2MgTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM4MTVcdWJkODBcdWIyOTQgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjNzc0XHVjNzIwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkMGMwXHVjNzdjXHVjNzQ0IFx1Yzc5MFx1YzhmYyBcdWJjMTRcdWFmYmNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWQwYzBcdWM3N2NcdWM3NDAgXHVhY2Y1XHVhZTA5XHVjNzc0IFx1YzIxOFx1YzY5NFx1Yjk3YyBcdWI1MzBcdWI3N2NcdWFjMDggXHVjMjE4IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjODE1XHViZDgwXHViMjk0IE1cdWM4ODVcdWI5NThcdWM3NTggXHViYjM2XHVjNzRjIFx1ZDBjMFx1Yzc3Y1x1YjljYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+aVx1YmM4OFx1YzlmOCBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHVjNzQwIEw8c3ViPmk8XC9zdWI+XHVhYzFjXHVjNzU4IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHVjNzQwIFx1ZDY4Y1x1YzgwNFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHVhYzcwXHViOWFjXHVjNjQwIFx1YzVmMFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWFlMDBcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWI5Y2MgXHVhZGY4IFx1YmIzNlx1Yzc0Y1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YWQ1MFx1Y2NiNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQwYzBcdWM3N2NcdWM3NDAgXHVhY2I5XHVjY2QwXHViM2M0IFx1YzBjMVx1YWQwMFx1YzVjNlx1YWNlMCwgXHVkNTVjIFx1YmIzNlx1Yzc0Y1x1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFjNzBcdWI5YWNcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWQwYzBcdWM3N2NcdWFjZmMgXHViYjM2XHVjNzRjIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzViNFx1YjVhNCBcdWQwYzBcdWM3N2NcdWI4NWNcdWIzYzQgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzcwXHViOWFjXHVjNzU4IFx1YWUzOFx1Yzc3NCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjNzBcdWI5YWNcdWM1ZDAgXHVjNmQwXHViNzk4IFx1YzgwMVx1ZDYwMFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzNlx1Yzc0YyBcdWQwYzBcdWM3N2NcdWM3NTggXHVjODg1XHViOTU4XHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAsMDAwLCAxICZsZTsgTSAmbGU7IDUwMDAsIDEgJmxlOyBcdWFjMDEgXHViYjM2XHVjNzRjIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFlMzhcdWM3NzQgJmxlOyA1MDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZGY4IFx1YzViNFx1YjVhNCBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHViODVjXHViM2M0IFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNWM2XHViMjk0IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQT1BMT1x1MDEwY0FWQU5KRSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya29cdTIwMWZzIEFTQ0lJIHN0cmVldCBpcyBtYWRlIG9mIE4gbG93ZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIFRoZSBjaXR5IGdvdmVybm1lbnQgb2NjYXNpb25hbGx5IHJlcGxhY2VzIHRoZSB0aWxlcyBpbiB0aGUgc3RyZWV0LiBIb3dldmVyLCB0aGUgbGV0dGVyIHRpbGVzIGFyZSBpbiBoaWdoIGRlbWFuZCwgc28gdGhlIGdvdmVybm1lbnQgaGFzIG9ubHkgTSBkaWZmZXJlbnQgdGlsZSBwYXR0ZXJucyBhdmFpbGFibGUuPFwvcD5cclxuXHJcbjxwPlRoZSBpPHN1cD50aDxcL3N1cD4gdGlsZSBwYXR0ZXJuIGNvbnNpc3RzIG9mIEw8c3ViPmk8XC9zdWI+IGxldHRlcnMuIEEgdGlsZSBjYW5ub3QgYmUgcm90YXRlZCBvciBicm9rZW4gaW50byBwaWVjZXMsIGFuZCBpdCBjYW4gb25seSBiZSBwbGFjZWQgc3VjaCB0aGF0IHRoZSB0aWxlIGxldHRlcnMgY29pbmNpZGUgd2l0aCB0aGUgY29udGlndW91cyBsZXR0ZXIgc3Vic2VxdWVuY2UgaW4gdGhlIHN0cmVldC4gVGlsZXMgY2FuIG92ZXJsYXAgYW5kIHdlIGNhbiB1c2UgbXVsdGlwbGUgdGlsZXMgb2YgdGhlIHNhbWUgcGF0dGVybi48XC9wPlxyXG5cclxuPHA+QSBzdHJlZXQgY2VsbCBpcyB1bnRpbGVhYmxlIGlmIGl0IGNhbm5vdCBiZSBjb3ZlcmVkIGJ5IGFueSB0aWxlLiBDb21wdXRlIHRoZSBudW1iZXIgb2YgdW50aWxlYWJsZSBjZWxscy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMzAwIDAwMCksIHRoZSBsZW5ndGggb2YgdGhlIHN0cmVldC48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gbG93ZXJjYXNlIEVuZ2xpc2ggbGV0dGVycywgdGhlIGxldHRlciBzZXF1ZW5jZSBpbiB0aGUgc3RyZWV0LjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBNICgxICZsZTsgTSAmbGU7IDUwMDApLCB0aGUgbnVtYmVyIG9mIHRpbGUgcGF0dGVybnMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyBjb250YWlucyBhIGRlc2NyaXB0aW9uIG9mIGEgdGlsZSBwYXR0ZXJuIHdpdGggbGVuZ3RoIEw8c3ViPmk8XC9zdWI+ICgxICZsZTsgTDxzdWI+aTxcL3N1Yj4gJmxlOyA1MDAwKS4gVGhlIHRpbGUgcGF0dGVybiBkZXNjcmlwdGlvbnMgY29uc2lzdCBvZiBsb3dlcmNhc2UgRW5nbGlzaCBsZXR0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG51bWJlciBvZiB1bnRpbGVhYmxlIGNlbGxzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013