시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 335 44 23 17.829%

문제

상근이네 집 앞의 아스키 거리는 알파벳 소문자가 적혀 있는 타일 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+XHVhYzFjXHVjNzU4IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHVjNzQwIFx1ZDY4Y1x1YzgwNFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHVhYzcwXHViOWFjXHVjNjQwIFx1YzVmMFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWFlMDBcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWI5Y2MgXHVhZGY4IFx1YmIzNlx1Yzc0Y1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1YWQ1MFx1Y2NiNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQwYzBcdWM3N2NcdWM3NDAgXHVhY2I5XHVjY2QwXHViM2M0IFx1YzBjMVx1YWQwMFx1YzVjNlx1YWNlMCwgXHVkNTVjIFx1YmIzNlx1Yzc0Y1x1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFjNzBcdWI5YWNcdWM1ZDAgXHVjMzY4XHVjNzg4XHViMjk0IFx1ZDBjMFx1Yzc3Y1x1YWNmYyBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjNWI0XHViNWE0IFx1ZDBjMFx1Yzc3Y1x1Yjg1Y1x1YjNjNCBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWNlNzhcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjNzBcdWI5YWNcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM3MFx1YjlhY1x1YzVkMCBcdWM2ZDBcdWI3OTggXHVjODAxXHVkNjAwXHVjODM4XHVjNzg4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM2XHVjNzRjIFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWM4ODVcdWI5NThcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YmIzNlx1Yzc0YyBcdWQwYzBcdWM3N2NcdWM1ZDAgXHVjODAxXHVkNjAwXHVjODM4XHVjNzg4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMwMCwwMDAsIDEgJmxlOyBNICZsZTsgNTAwMCwgMSAmbGU7IFx1YWMwMSBcdWJiMzZcdWM3NGMgXHVkMGMwXHVjNzdjXHVjNzU4IFx1YWUzOFx1Yzc3NCAmbGU7IDUwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjggXHVjNWI0XHViNWE0IFx1YmIzNlx1Yzc0YyBcdWQwYzBcdWM3N2NcdWI4NWNcdWIzYzQgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVkMGMwXHVjNzdjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPUExPXHUwMTBjQVZBTkpFIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrb1x1MjAxZnMgQVNDSUkgc3RyZWV0IGlzIG1hZGUgb2YgTiBsb3dlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gVGhlIGNpdHkgZ292ZXJubWVudCBvY2Nhc2lvbmFsbHkgcmVwbGFjZXMgdGhlIHRpbGVzIGluIHRoZSBzdHJlZXQuIEhvd2V2ZXIsIHRoZSBsZXR0ZXIgdGlsZXMgYXJlIGluIGhpZ2ggZGVtYW5kLCBzbyB0aGUgZ292ZXJubWVudCBoYXMgb25seSBNIGRpZmZlcmVudCB0aWxlIHBhdHRlcm5zIGF2YWlsYWJsZS48XC9wPlxyXG5cclxuPHA+VGhlIGk8c3VwPnRoPFwvc3VwPiB0aWxlIHBhdHRlcm4gY29uc2lzdHMgb2YgTDxzdWI+aTxcL3N1Yj4gbGV0dGVycy4gQSB0aWxlIGNhbm5vdCBiZSByb3RhdGVkIG9yIGJyb2tlbiBpbnRvIHBpZWNlcywgYW5kIGl0IGNhbiBvbmx5IGJlIHBsYWNlZCBzdWNoIHRoYXQgdGhlIHRpbGUgbGV0dGVycyBjb2luY2lkZSB3aXRoIHRoZSBjb250aWd1b3VzIGxldHRlciBzdWJzZXF1ZW5jZSBpbiB0aGUgc3RyZWV0LiBUaWxlcyBjYW4gb3ZlcmxhcCBhbmQgd2UgY2FuIHVzZSBtdWx0aXBsZSB0aWxlcyBvZiB0aGUgc2FtZSBwYXR0ZXJuLjxcL3A+XHJcblxyXG48cD5BIHN0cmVldCBjZWxsIGlzIHVudGlsZWFibGUgaWYgaXQgY2Fubm90IGJlIGNvdmVyZWQgYnkgYW55IHRpbGUuIENvbXB1dGUgdGhlIG51bWJlciBvZiB1bnRpbGVhYmxlIGNlbGxzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgc3RyZWV0LjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBsb3dlcmNhc2UgRW5nbGlzaCBsZXR0ZXJzLCB0aGUgbGV0dGVyIHNlcXVlbmNlIGluIHRoZSBzdHJlZXQuPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE0gKDEgJmxlOyBNICZsZTsgNTAwMCksIHRoZSBudW1iZXIgb2YgdGlsZSBwYXR0ZXJucy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGNvbnRhaW5zIGEgZGVzY3JpcHRpb24gb2YgYSB0aWxlIHBhdHRlcm4gd2l0aCBsZW5ndGggTDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBMPHN1Yj5pPFwvc3ViPiAmbGU7IDUwMDApLiBUaGUgdGlsZSBwYXR0ZXJuIGRlc2NyaXB0aW9ucyBjb25zaXN0IG9mIGxvd2VyY2FzZSBFbmdsaXNoIGxldHRlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHVudGlsZWFibGUgY2VsbHMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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