시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3329108976935.002%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

4 11
cAda
AbrAcadAbRa

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE1OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTAgXHVkNTc0XHViM2M1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5YzhcdWM1N2MgXHViYjM4XHVjNzkwXHViOTdjIFx1ZDU3NFx1YjNjNVx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDAgXHVjNjA4XHVjMGMxIFx1YzY3OFx1Yjg1YyBcdWM1YjRcdWI4MjRcdWM2YjQgXHVjNzdjXHVjNzc0XHViMmU0LiBcdWQ2MDRcdWM3YWNcdWM1ZDBcdWIzYzQgXHViNzNiXHVjNzc0IFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWJjMWRcdWQ2MDBcdWM5YzQgXHViOWM4XHVjNTdjIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWFjNzBcdWM3NTggXHVjNWM2XHViMjk0IFx1YzJlNFx1YzgxNVx1Yzc3NFx1YmE3MCwgXHVhZGY4XHViMDk4XHViOWM4IFx1ZDU3NFx1YjNjNVx1YzVkMCBcdWM5YzRcdWNjOTlcdWM3NzQgXHVjMmRjXHVjNzkxXHViNDFjIFx1YzljMFx1YjI5NCAzMFx1YzVlYyBcdWIxNDRcdWIzYzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjNTdjIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWMxOGNcdWI5YWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzVlY1x1YjdlYyBcdWM4ODVcdWI5NThcdWM3NTggXHVhZGY4XHViOWJjXHVhZTAwXHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1YWUwMFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YWNiMFx1ZDU2OVx1ZDU2OFx1YzczY1x1Yjg1Y1x1YzM2OCBcdWIyZThcdWM1YjRcdWI5N2MgXHVkNjE1XHVjMTMxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM1N2MgXHViYjM4XHVjNzkwIFx1ZDU3NFx1YjNjNVx1Yzc0NCBcdWM1YjRcdWI4MzVcdWFjOGMgXHVkNTU4XHViMjk0IFx1YzY5NFx1Yzc3OCBcdWM5MTEgXHVkNTU4XHViMDk4XHViMjk0IFx1YmMxNFx1Yjg1YyBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzdkXHViMjk0IFx1YzIxY1x1YzExY1x1Yzc3NFx1YjJlNC4gXHViOWM4XHVjNTdjIFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM0ZjBcdWIyOTQgXHVhY2UwXHViMzAwXHVjNzc4XHViNGU0XHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWFlMzBcdWI4NWRcdWQ1NjAgXHViNTRjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWFkZGNcdWNlNTkgXHViMzAwXHVjMmUwLCBcdWFkZjhcdWI0ZTRcdWM3NzQgXHViY2Y0XHVhZTMwXHVjNWQwIFx1Yzg4Ylx1YWM4YyBcdWJjZjRcdWM3NzRcdWIzYzRcdWI4NWQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFlMDBcdWM3OTBcdWI0ZTRcdWM3NDQgXHVjNTQ0XHViYjM0XHViODA3XHVhYzhjXHViMDk4IFx1YmMzMFx1YzVmNFx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViODA3XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NzQgXHViOWM4XHVjNTdjIFx1YWUzMFx1Yjg1ZFx1YzVkMFx1YzExYyBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YWMwMSBcdWFkZjhcdWI5YmNcdWFlMDBcdWM3OTBcdWI0ZTRcdWM3NTggXHViYzFjXHVjNzRjXHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWFkZjggXHViMmU4XHVjNWI0XHViOTdjIFx1YzJlNFx1YzgxY1x1Yjg1YyBcdWJjMWNcdWM3NGNcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWM1NGMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWMxNDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBXXHViNzdjXHViMjk0IFx1ZDJiOVx1YzgxNSBcdWIyZThcdWM1YjRcdWI5N2MgXHViYzFjXHVhZDc0IFx1YWUzMFx1Yjg1ZFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWNjM2VcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjggXHViMmU4XHVjNWI0XHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWFjMDEgXHVhZTAwXHVjNzkwXHViNGU0XHVjNzQwIFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWM1NGNcdWFjZTAgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWM3NzRcdWFjODNcdWM3NzQgXHVhY2UwXHViMzAwIFx1YWUzMFx1Yjg1ZFx1YzVkMCBcdWM1YjRcdWI1YTQgXHVkNjE1XHVkMGRjXHViODVjIFx1YzIyOFx1YzViNCBcdWM3ODhcdWIyOTRcdWM5YzBcdWIyOTQgXHViMmU0IFx1YzU0Y1x1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPldcdWI5N2MgXHVjNzc0XHViOGU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBnXHVhYzFjXHVjNzU4IFx1YWRmOFx1YjliY1x1YmIzOFx1Yzc5MFx1YzY0MCwgXHVjNWYwXHVhZDZjIFx1YjMwMFx1YzBjMVx1Yzc3OCBcdWJjYmRcdWQ2NTRcdWM1ZDAgXHVhZTMwXHViODVkXHViNDFjIFx1YjljOFx1YzU3YyBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIyZThcdWM1YjQgV1x1YWMwMCBcdWI5YzhcdWM1N2MgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YWMwMFx1YzlkM1x1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjOTg5LCBcdWJiMzhcdWM3OTBcdWM1ZjQmbmJzcDsgU1x1YzU0OFx1YzVkMFx1YzExYyBcdWJiMzhcdWM3OTBcdWM1ZjQgV1x1Yzc1OCBcdWMyMWNcdWM1ZjQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjYzNlXHVhY2UwXHVjNzkwIFx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjQgV1x1Yzc1OCBcdWFlMzhcdWM3NzQgZ1x1YzY0MCBcdWJjMWNcdWFkNzRcdWI0MWMgXHViY2JkXHVkNjU0XHVjNWQwXHVjMTFjIFx1Y2Q5NFx1Y2Q5Y1x1ZDU1YyBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1Yzc1OCBcdWFlMzhcdWM3NzQgfFN8XHVhYzAwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmxlO2cmbGU7MzAwMCwmbmJzcDsgZyZsZTt8U3wmbGU7MywwMDAsMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFcsIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgU1x1Yzc1OCBcdWMyZTRcdWM4MWMgXHViMGI0XHVjNmE5XHVjNzc0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHViYTcwLCBcdWIzMDBcdWMxOGNcdWJiMzhcdWM3OTBcdWI5N2MgXHVhZDZjXHViZDg0XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgV1x1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NzQgUyBcdWM1NDhcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNjE1XHVkMGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTU5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlY2lwaGVyaW5nIHRoZSBNYXlhbiBXcml0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5EZWNpcGhlcmluZyB0aGUgTWF5YW4gd3JpdGluZyBoYXMgcHJvdmVuIHRvIGJlIGEgaGFyZGVyIHRhc2sgdGhhbiBhbnRpY2lwYXRlZCBieSB0aGUgZWFybHkgaW52ZXN0aWdhdGlvbnMuIEFmdGVyIGFsbW9zdCB0d28gaHVuZHJlZCB5ZWFycywgdmVyeSBsaXR0bGUgb2YgaXQgd2FzIGFjdHVhbGx5IHVuZGVyc3Rvb2QuIEl0IGhhcyBiZWVuIG9ubHkgaW4gdGhlIGxhc3QgdGhyZWUgZGVjYWRlcyB0aGF0IHJlYWwgYWR2YW5jZXMgaGF2ZSBiZWVuIG1hZGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1heWFuIHdyaXRpbmcgaXMgYmFzZWQgb24gc21hbGwgZHJhd2luZ3Mga25vd24gYXMgZ2x5cGhzIHdoaWNoIHJlcHJlc2VudCBzb3VuZHMuIE1heWFuIHdvcmRzIGFyZSBub3JtYWxseSB3cml0dGVuIGFzIGdseXBocyBwdXQgdG9nZXRoZXIgYXQgdmFyaW91cyBwb3NpdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSBvZiBzZXZlcmFsIHByb2JsZW1zIGluIGRlY2lwaGVyaW5nIE1heWFuIHdyaXRpbmcgYXJpc2VzIGluIHRoZSBvcmRlciBvZiByZWFkaW5nLiBXaGVuIHBsYWNpbmcgc2V2ZXJhbCBnbHlwaHMgaW4gb3JkZXIgdG8gZm9ybSBhIHdvcmQsIE1heWFuIHdyaXRlcnMgc29tZXRpbWVzIGRlY2lkZWQgdGhlIHBvc2l0aW9uIGJhc2VkIG1vcmUgb24gdGhlaXIgb3duIGVzdGhldGljIHZpZXdzIHRoYW4gb24gYW55IHBhcnRpY3VsYXIgcnVsZS4gVGhpcyBsZWFkcyB0byB0aGUgZmFjdCB0aGF0LCBldmVuIHRob3VnaCB0aGUgc291bmQgZm9yIG1hbnkgZ2x5cGhzIGlzIGtub3duLCBzb21ldGltZXMgYXJjaGFlb2xvZ2lzdHMgYXJlIG5vdCBzdXJlIGhvdyB0byBwcm9ub3VuY2UgYSB3cml0dGVuIHdvcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBhcmNoYWVvbG9naXN0cyBhcmUgbG9va2luZyBmb3IgYSBzcGVjaWFsIHdvcmQgVy4gVGhleSBrbm93IHRoZSBnbHlwaHMgZm9yIGl0LCBidXQgdGhleSBkb24mcnNxdW87dCBrbm93IGFsbCB0aGUgcG9zc2libGUgd2F5cyBvZiBhcnJhbmdpbmcgdGhlbS4gU2luY2UgdGhleSBrbmV3IHlvdSB3ZXJlIGNvbWluZyB0byBJT0kmcnNxdW87MDYsIHRoZXkgaGF2ZSBhc2tlZCBmb3IgeW91ciBoZWxwLiBUaGV5IHdpbGwgcHJvdmlkZSB5b3Ugd2l0aCB0aGUgZyBnbHlwaHMgZnJvbSBXIGFuZCBhIHNlcXVlbmNlIFMgb2YgYWxsIHRoZSBnbHlwaHMgKGluIHRoZSBvcmRlciB0aGV5IGFwcGVhcikgaW4gdGhlIGNhcnZpbmdzIHRoZXkgYXJlIHN0dWR5aW5nLiBIZWxwIHRoZW0gYnkgY291bnRpbmcgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBhcHBlYXJhbmNlcyBvZiB0aGUgd29yZCBXLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGdseXBocyBmb3IgVyBhbmQgdGhlIHNlcXVlbmNlIFMgb2YgZ2x5cGhzIGluIHRoZSBjYXJ2aW5ncywgY291bnRzIHRoZSBudW1iZXIgb2YgcG9zc2libGUgYXBwZWFyYW5jZXMgb2YgVyBpbiBTOyB0aGF0IGlzLCBldmVyeSBzZXF1ZW5jZSBvZiBjb25zZWN1dGl2ZSBnIGdseXBocyBpbiBTIHRoYXQgaXMgYSBwZXJtdXRhdGlvbiBvZiB0aGUgZ2x5cGhzIGluIFcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxJTkUgMTogQ29udGFpbnMgMiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgdGhhdCByZXByZXNlbnQgZyBhbmQgfFN8LjxcL2xpPlxyXG5cdDxsaT5MSU5FIDI6IENvbnRhaW5zIGcgY29uc2VjdXRpdmUgY2hhcmFjdGVycyB0aGF0IHJlcHJlc2VudCB0aGUgZ2x5cGhzIGluIFcuIFZhbGlkIGNoYXJhY3RlcnMgYXJlICZsc3F1bzthJnJzcXVvOy0mbHNxdW87eiZyc3F1bzsgYW5kICZsc3F1bztBJnJzcXVvOy0mbHNxdW87WiZyc3F1bzs7IHVwcGVyY2FzZSBhbmQgbG93ZXJjYXNlIGNoYXJhY3RlcnMgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MSU5FIDM6IENvbnRhaW5zIHxTfCBjb25zZWN1dGl2ZSBjaGFyYWN0ZXJzIHRoYXQgcmVwcmVzZW50IHRoZSBnbHlwaHMgaW4gdGhlIGNhcnZpbmdzLiBWYWxpZCBjaGFyYWN0ZXJzIGFyZSAmbHNxdW87YSZyc3F1bzstJmxzcXVvO3omcnNxdW87IGFuZCAmbHNxdW87QSZyc3F1bzstJmxzcXVvO1omcnNxdW87OyB1cHBlcmNhc2UgYW5kIGxvd2VyY2FzZSBjaGFyYWN0ZXJzIGFyZSBjb25zaWRlcmVkIGRpZmZlcmVudC4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TElORSAxOiBNdXN0IGNvbnRhaW4gdGhlIGNvdW50IG9mIHBvc3NpYmxlIGFwcGVhcmFuY2VzIG9mIFcgaW4gUy4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2006 > Day 1 1번

  • 문제를 번역한 사람: author5