시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 153 58 46 56.098%

문제

마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.

마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.

마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.

고고학자들은 W라는 특정 단어를 발굴 기록으로부터 찾고 있다. 그 단어를 구성하는 각 글자들은 무엇인지 알고 있지만, 이것이 고대 기록에 어떤 형태로 숨어 있는지는 다 알지 못한다.

W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

입력

첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000,  g≤|S|≤3,000,000) 둘째 줄에 g, 셋째 줄에 S의 실제 내용이 들어있다. 모든 문자열은 알파벳으로 이루어지며, 대소문자를 구분한다.

출력

첫째 줄에 W의 순열이 S 안에 있을 수 있는 형태의 개수를 출력한다.

예제 입력 1

4 11
cAda
AbrAcadAbRa

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE1OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTAgXHVkNTc0XHViM2M1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5YzhcdWM1N2MgXHViYjM4XHVjNzkwXHViOTdjIFx1ZDU3NFx1YjNjNVx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDAgXHVjNjA4XHVjMGMxIFx1YzY3OFx1Yjg1YyBcdWM1YjRcdWI4MjRcdWM2YjQgXHVjNzdjXHVjNzc0XHViMmU0LiBcdWQ2MDRcdWM3YWNcdWM1ZDBcdWIzYzQgXHViNzNiXHVjNzc0IFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWJjMWRcdWQ2MDBcdWM5YzQgXHViOWM4XHVjNTdjIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWFjNzBcdWM3NTggXHVjNWM2XHViMjk0IFx1YzJlNFx1YzgxNVx1Yzc3NFx1YmE3MCwgXHVhZGY4XHViMDk4XHViOWM4IFx1ZDU3NFx1YjNjNVx1YzVkMCBcdWM5YzRcdWNjOTlcdWM3NzQgXHVjMmRjXHVjNzkxXHViNDFjIFx1YzljMFx1YjI5NCAzMFx1YzVlYyBcdWIxNDRcdWIzYzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC48XC9wPlxyXG48cD5cdWI5YzhcdWM1N2MgXHViYjM4XHVjNzkwXHViMjk0IFx1YzE4Y1x1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNWVjXHViN2VjIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWFlMDBcdWM3OTBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVhZTAwXHVjNzkwXHViNGU0XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHVhY2IwXHVkNTY5XHVkNTY4XHVjNzNjXHViODVjXHVjMzY4IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWQ2MTVcdWMxMzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHViOWM4XHVjNTdjIFx1YmIzOFx1Yzc5MCBcdWQ1NzRcdWIzYzVcdWM3NDQgXHVjNWI0XHViODM1XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWM2OTRcdWM3NzggXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWJjMTRcdWI4NWMgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3ZFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuIFx1YjljOFx1YzU3YyBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjNGYwXHViMjk0IFx1YWNlMFx1YjMwMFx1Yzc3OFx1YjRlNFx1Yzc0MCBcdWIyZThcdWM1YjRcdWI5N2MgXHVhZTMwXHViODVkXHVkNTYwIFx1YjU0YyBcdWQyYjlcdWM4MTVcdWQ1NWMgXHVhZGRjXHVjZTU5IFx1YjMwMFx1YzJlMCwgXHVhZGY4XHViNGU0XHVjNzc0IFx1YmNmNFx1YWUzMFx1YzVkMCBcdWM4OGJcdWFjOGMgXHViY2Y0XHVjNzc0XHViM2M0XHViODVkIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVhZTAwXHVjNzkwXHViNGU0XHVjNzQ0IFx1YzU0NFx1YmIzNFx1YjgwN1x1YWM4Y1x1YjA5OCBcdWJjMzBcdWM1ZjRcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhY2UwXHVhY2UwXHVkNTU5XHVjNzkwXHViNGU0XHVjNzc0IFx1YjljOFx1YzU3YyBcdWFlMzBcdWI4NWRcdWM1ZDBcdWMxMWMgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFjMDEgXHVhZGY4XHViOWJjXHVhZTAwXHVjNzkwXHViNGU0XHVjNzU4IFx1YmMxY1x1Yzc0Y1x1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZGY4IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWMyZTRcdWM4MWNcdWI4NWMgXHViYzFjXHVjNzRjXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMTQ4XHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBXXHViNzdjXHViMjk0IFx1ZDJiOVx1YzgxNSBcdWIyZThcdWM1YjRcdWI5N2MgXHViYzFjXHVhZDc0IFx1YWUzMFx1Yjg1ZFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWNjM2VcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjggXHViMmU4XHVjNWI0XHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWFjMDEgXHVhZTAwXHVjNzkwXHViNGU0XHVjNzQwIFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWM3NzRcdWFjODNcdWM3NzQgXHVhY2UwXHViMzAwIFx1YWUzMFx1Yjg1ZFx1YzVkMCBcdWM1YjRcdWI1YTQgXHVkNjE1XHVkMGRjXHViODVjIFx1YzIyOFx1YzViNCBcdWM3ODhcdWIyOTRcdWM5YzBcdWIyOTQgXHViMmU0IFx1YzU0Y1x1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+V1x1Yjk3YyBcdWM3NzRcdWI4ZThcdWFjZTAgXHVjNzg4XHViMjk0IGdcdWFjMWNcdWM3NTggXHVhZGY4XHViOWJjXHViYjM4XHVjNzkwXHVjNjQwLCBcdWM1ZjBcdWFkNmMgXHViMzAwXHVjMGMxXHVjNzc4IFx1YmNiZFx1ZDY1NFx1YzVkMCBcdWFlMzBcdWI4NWRcdWI0MWMgXHViOWM4XHVjNTdjIFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjJlOFx1YzViNCBXXHVhYzAwIFx1YjljOFx1YzU3YyBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM5ODksIFx1YmIzOFx1Yzc5MFx1YzVmNCZuYnNwOyBTXHVjNTQ4XHVjNWQwXHVjMTFjIFx1YmIzOFx1Yzc5MFx1YzVmNCBXXHVjNzU4IFx1YzIxY1x1YzVmNCBcdWM5MTEgXHVkNTU4XHViMDk4XHVhYzAwIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2UwXHVhY2UwXHVkNTU5XHVjNzkwXHViNGU0XHVjNzc0IFx1Y2MzZVx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0IFdcdWM3NTggXHVhZTM4XHVjNzc0IGdcdWM2NDAgXHViYzFjXHVhZDc0XHViNDFjIFx1YmNiZFx1ZDY1NFx1YzVkMFx1YzExYyBcdWNkOTRcdWNkOWNcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM3NTggXHVhZTM4XHVjNzc0IHxTfFx1YWMwMCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsZTtnJmxlOzMwMDAsJm5ic3A7IGcmbGU7fFN8JmxlOzMsMDAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBnLCBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIFNcdWM3NTggXHVjMmU0XHVjODFjIFx1YjBiNFx1YzZhOVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YmE3MCwgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHViOTdjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgV1x1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NzQgUyBcdWM1NDhcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNjE1XHVkMGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNTkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVjaXBoZXJpbmcgdGhlIE1heWFuIFdyaXRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkRlY2lwaGVyaW5nIHRoZSBNYXlhbiB3cml0aW5nIGhhcyBwcm92ZW4gdG8gYmUgYSBoYXJkZXIgdGFzayB0aGFuIGFudGljaXBhdGVkIGJ5IHRoZSBlYXJseSBpbnZlc3RpZ2F0aW9ucy4gQWZ0ZXIgYWxtb3N0IHR3byBodW5kcmVkIHllYXJzLCB2ZXJ5IGxpdHRsZSBvZiBpdCB3YXMgYWN0dWFsbHkgdW5kZXJzdG9vZC4gSXQgaGFzIGJlZW4gb25seSBpbiB0aGUgbGFzdCB0aHJlZSBkZWNhZGVzIHRoYXQgcmVhbCBhZHZhbmNlcyBoYXZlIGJlZW4gbWFkZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWF5YW4gd3JpdGluZyBpcyBiYXNlZCBvbiBzbWFsbCBkcmF3aW5ncyBrbm93biBhcyBnbHlwaHMgd2hpY2ggcmVwcmVzZW50IHNvdW5kcy4gTWF5YW4gd29yZHMgYXJlIG5vcm1hbGx5IHdyaXR0ZW4gYXMgZ2x5cGhzIHB1dCB0b2dldGhlciBhdCB2YXJpb3VzIHBvc2l0aW9ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T25lIG9mIHNldmVyYWwgcHJvYmxlbXMgaW4gZGVjaXBoZXJpbmcgTWF5YW4gd3JpdGluZyBhcmlzZXMgaW4gdGhlIG9yZGVyIG9mIHJlYWRpbmcuIFdoZW4gcGxhY2luZyBzZXZlcmFsIGdseXBocyBpbiBvcmRlciB0byBmb3JtIGEgd29yZCwgTWF5YW4gd3JpdGVycyBzb21ldGltZXMgZGVjaWRlZCB0aGUgcG9zaXRpb24gYmFzZWQgbW9yZSBvbiB0aGVpciBvd24gZXN0aGV0aWMgdmlld3MgdGhhbiBvbiBhbnkgcGFydGljdWxhciBydWxlLiBUaGlzIGxlYWRzIHRvIHRoZSBmYWN0IHRoYXQsIGV2ZW4gdGhvdWdoIHRoZSBzb3VuZCBmb3IgbWFueSBnbHlwaHMgaXMga25vd24sIHNvbWV0aW1lcyBhcmNoYWVvbG9naXN0cyBhcmUgbm90IHN1cmUgaG93IHRvIHByb25vdW5jZSBhIHdyaXR0ZW4gd29yZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGFyY2hhZW9sb2dpc3RzIGFyZSBsb29raW5nIGZvciBhIHNwZWNpYWwgd29yZCBXLiBUaGV5IGtub3cgdGhlIGdseXBocyBmb3IgaXQsIGJ1dCB0aGV5IGRvbiZyc3F1bzt0IGtub3cgYWxsIHRoZSBwb3NzaWJsZSB3YXlzIG9mIGFycmFuZ2luZyB0aGVtLiBTaW5jZSB0aGV5IGtuZXcgeW91IHdlcmUgY29taW5nIHRvIElPSSZyc3F1bzswNiwgdGhleSBoYXZlIGFza2VkIGZvciB5b3VyIGhlbHAuIFRoZXkgd2lsbCBwcm92aWRlIHlvdSB3aXRoIHRoZSBnIGdseXBocyBmcm9tIFcgYW5kIGEgc2VxdWVuY2UgUyBvZiBhbGwgdGhlIGdseXBocyAoaW4gdGhlIG9yZGVyIHRoZXkgYXBwZWFyKSBpbiB0aGUgY2FydmluZ3MgdGhleSBhcmUgc3R1ZHlpbmcuIEhlbHAgdGhlbSBieSBjb3VudGluZyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIGFwcGVhcmFuY2VzIG9mIHRoZSB3b3JkIFcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgZ2x5cGhzIGZvciBXIGFuZCB0aGUgc2VxdWVuY2UgUyBvZiBnbHlwaHMgaW4gdGhlIGNhcnZpbmdzLCBjb3VudHMgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBhcHBlYXJhbmNlcyBvZiBXIGluIFM7IHRoYXQgaXMsIGV2ZXJ5IHNlcXVlbmNlIG9mIGNvbnNlY3V0aXZlIGcgZ2x5cGhzIGluIFMgdGhhdCBpcyBhIHBlcm11dGF0aW9uIG9mIHRoZSBnbHlwaHMgaW4gVy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkxJTkUgMTogQ29udGFpbnMgMiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgdGhhdCByZXByZXNlbnQgZyBhbmQgfFN8LjxiciBcLz5cclxuTElORSAyOiBDb250YWlucyBnIGNvbnNlY3V0aXZlIGNoYXJhY3RlcnMgdGhhdCByZXByZXNlbnQgdGhlIGdseXBocyBpbiBXLiBWYWxpZCBjaGFyYWN0ZXJzIGFyZSAmbHNxdW87YSZyc3F1bzstJmxzcXVvO3omcnNxdW87IGFuZCAmbHNxdW87QSZyc3F1bzstJmxzcXVvO1omcnNxdW87OyB1cHBlcmNhc2UgYW5kIGxvd2VyY2FzZSBjaGFyYWN0ZXJzIGFyZSBjb25zaWRlcmVkIGRpZmZlcmVudC4mbmJzcDs8YnIgXC8+XHJcbkxJTkUgMzogQ29udGFpbnMgfFN8IGNvbnNlY3V0aXZlIGNoYXJhY3RlcnMgdGhhdCByZXByZXNlbnQgdGhlIGdseXBocyBpbiB0aGUgY2FydmluZ3MuIFZhbGlkIGNoYXJhY3RlcnMgYXJlICZsc3F1bzthJnJzcXVvOy0mbHNxdW87eiZyc3F1bzsgYW5kICZsc3F1bztBJnJzcXVvOy0mbHNxdW87WiZyc3F1bzs7IHVwcGVyY2FzZSBhbmQgbG93ZXJjYXNlIGNoYXJhY3RlcnMgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD4xICZsZTsgZyAmbGU7IDMgMDAwIHRoZSBudW1iZXIgb2YgZ2x5cGhzIGluIFc8YnIgXC8+XHJcbmcgJmxlOyB8U3wgJmxlOyAzIDAwMCAwMDAgd2hlcmUgfFN8IGlzIHRoZSBudW1iZXIgb2YgZ2x5cGhzIGluIHRoZSBzZXF1ZW5jZSBTPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+TElORSAxOiBNdXN0IGNvbnRhaW4gdGhlIGNvdW50IG9mIHBvc3NpYmxlIGFwcGVhcmFuY2VzIG9mIFcgaW4gUy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2006 1번

  • 문제를 번역한 사람: author5