시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 117 53 34 43.038%

문제

현대 분자 생물학에서 유전자 정보는 모두 DNA로 인코딩해서 나타낸다. 컴퓨터 과학에서는 DNA를 {A, G, T, C}로만 이루어진 길이가 아주 긴 문자열로 표현한다.

다른 것보다 많이 등장하는 DNA(부분문자열) 패턴을 찾는 일은 유전병 연구에서 매우 중요하다. 이 문제에서는 합성적으로 같은(compositionally equivalent) 부분문자열을 찾으려고 한다. 두 문자열 P, Q에서 등장하는 네 문자 {A, G, T, C}의 개수가 모두 동일할 때, P와 Q는 합성적으로 같은 문자열이라고 한다. 예를 들어, P="ATTATGC"와 Q="GTATCTA"는 P에서 등장하는 'A', G', 'C', 'T'의 개수가 Q와 같기 때문에, 두 문자열은 합성적으로 같다고 한다. "TTGCA"는 "TGCCA"와 합성적으로 같지 않다.

k-Major Composition Substring, 줄여서 k-MCS는 길이가 k인 부분 문자열중에서 가장 많이 등장하는 합성적으로 같은 부분문자열이다. 한 DNA의 k-MCS는 유일하지 않을 수도 있다. k-부분문자열은 길이가 k인 부분문자열을 나타낸다.

예를 들어, 길이가 14인 DNA 문자열 W="GCAGGAGCGCCAGG"에서 합성적으로 다른 3-부분문자열은 GCA, CAG, GGa, GAG, ..., CAG, AGG가 있다. "AGG"는 총 4번 (AGG, GGA, GAG, AGG) 등장하기 때문에, 이 문자열의 3-MCS가 된다. W에서 4번 보다 많이 등장하는 3-부분문자열은 없다.

DNA 문자열과 k이 주어졌을 때, k-MCS가 몇 번 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 k(1 ≤ k ≤ 600)이고, 그 다음에 DNA 문자열 W가 주어진다. (10 ≤ |W| ≤ 60000)

출력

각 테스트 케이스 마다, 입력으로 주어진 W에서 k-MCS가 몇 번 등장하는지 출력한다.

예제 입력 1

3
3 GCAGGAGCGCCAGG
4 AGTCCTTAGAG
5 GGGAGGGGGGGTGGGGGGGGT

예제 출력 1

4
2
7

힌트

W3sicHJvYmxlbV9pZCI6Ijg5MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJNQ1MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDYwNFx1YjMwMCBcdWJkODRcdWM3OTAgXHVjMGRkXHViYjNjXHVkNTU5XHVjNWQwXHVjMTFjIFx1YzcyMFx1YzgwNFx1Yzc5MCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViYWE4XHViNDUwIEROQVx1Yjg1YyBcdWM3NzhcdWNmNTRcdWI1MjlcdWQ1NzRcdWMxMWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVhY2ZjXHVkNTU5XHVjNWQwXHVjMTFjXHViMjk0IEROQVx1Yjk3YyB7QSwgRywgVCwgQ31cdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM1NDRcdWM4ZmMgXHVhZTM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yjk3OCBcdWFjODNcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBETkEoXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0KSBcdWQzMjhcdWQxMzRcdWM3NDQgXHVjYzNlXHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWM3MjBcdWM4MDRcdWJjZDEgXHVjNWYwXHVhZDZjXHVjNWQwXHVjMTFjIFx1YjllNFx1YzZiMCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNTY5XHVjMTMxXHVjODAxXHVjNzNjXHViODVjIFx1YWMxOVx1Yzc0MChjb21wb3NpdGlvbmFsbHkgZXF1aXZhbGVudCkgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjQgUCwgUVx1YzVkMFx1YzExYyBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViMTI0IFx1YmIzOFx1Yzc5MCB7QSwgRywgVCwgQ31cdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWIzZDlcdWM3N2NcdWQ1NjAgXHViNTRjLCBQXHVjNjQwIFFcdWIyOTQgXHVkNTY5XHVjMTMxXHVjODAxXHVjNzNjXHViODVjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBQPSZxdW90O0FUVEFUR0MmcXVvdDtcdWM2NDAgUT0mcXVvdDtHVEFUQ1RBJnF1b3Q7XHViMjk0IFBcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0ICYjMzk7QSYjMzk7LCBHJiMzOTssICYjMzk7QyYjMzk7LCAmIzM5O1QmIzM5O1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgUVx1YzY0MCBcdWFjMTlcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1ZDU2OVx1YzEzMVx1YzgwMVx1YzczY1x1Yjg1YyBcdWFjMTlcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiAmcXVvdDtUVEdDQSZxdW90O1x1YjI5NCAmcXVvdDtUR0NDQSZxdW90O1x1YzY0MCBcdWQ1NjlcdWMxMzFcdWM4MDFcdWM3M2NcdWI4NWMgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+ay1NYWpvciBDb21wb3NpdGlvbiBTdWJzdHJpbmcsIFx1YzkwNFx1YzVlY1x1YzExYyBrLU1DU1x1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAga1x1Yzc3OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NzQgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1ZDU2OVx1YzEzMVx1YzgwMVx1YzczY1x1Yjg1YyBcdWFjMTlcdWM3NDAgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWQ1NWMgRE5BXHVjNzU4IGstTUNTXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gay1cdWJkODBcdWJkODRcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVhZTM4XHVjNzc0XHVhYzAwIGtcdWM3NzggXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhZTM4XHVjNzc0XHVhYzAwIDE0XHVjNzc4IEROQSBcdWJiMzhcdWM3OTBcdWM1ZjQgVz0mcXVvdDtHQ0FHR0FHQ0dDQ0FHRyZxdW90O1x1YzVkMFx1YzExYyBcdWQ1NjlcdWMxMzFcdWM4MDFcdWM3M2NcdWI4NWMgXHViMmU0XHViOTc4IDMtXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIEdDQSwgQ0FHLCBHR2EsIEdBRywgLi4uLCBDQUcsIEFHR1x1YWMwMCBcdWM3ODhcdWIyZTQuICZxdW90O0FHRyZxdW90O1x1YjI5NCBcdWNkMWQgNFx1YmM4OCAoQUdHLCBHR0EsIEdBRywgQUdHKSBcdWI0ZjFcdWM3YTVcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IDMtTUNTXHVhYzAwIFx1YjQxY1x1YjJlNC4gV1x1YzVkMFx1YzExYyA0XHViYzg4IFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NzQgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IDMtXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+RE5BIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YWNmYyBrXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIGstTUNTXHVhYzAwIFx1YmE4NyBcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBrKDEgJmxlOyBrICZsZTsgNjAwKVx1Yzc3NFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBETkEgXHViYjM4XHVjNzkwXHVjNWY0IFdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMTAgJmxlOyB8V3wgJmxlOyA2MDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgV1x1YzVkMFx1YzExYyBrLU1DU1x1YWMwMCBcdWJhODcgXHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODkzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1DUyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gbW9kZXJuIG1vbGVjdWxhciBiaW9sb2d5IHRoZSBnZW5vbWUgb2YgYW4gb3JnYW5pc20gaXMgaXRzIGhlcmVkaXRhcnkgaW5mb3JtYXRpb24gZW5jb2RlZCBpbiBETkEuIFRoZSBnZW5vbWUgaW5jbHVkZXMgYm90aCB0aGUgZ2VuZXMgYW5kIHRoZSBub24tY29kaW5nIHNlcXVlbmNlcyBvZiB0aGUgRE5BLiBJbiB0aGUgdmlldyBvZiBjb21wdXRlciBzY2llbmNlLCB0aGUgZ2Vub21lIGNhbiBiZSByZWdhcmRlZCBhcyBhIHZlcnkgbG9uZyBzdHJpbmcgY29uc2lzdGluZyBvZiBvbmx5IGZvdXIgbGV0dGVycyB7QSxHLFQsQ30uJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkluIG9yZGVyIHRvIHN0dWR5IHNwZWNpZmljIGdlbmV0aWMgZGlzZWFzZXMsIGl0IGlzIHZlcnkgaW1wb3J0YW50IHRvIGV4YW1pbmUgaWYgdGhlcmUgYXJlIEROQSAoc3Vic3RyaW5nKSBwYXR0ZXJucyB3aGljaCBhcHBlYXIgbW9yZSBmcmVxdWVudGx5IHRoYW4gb3RoZXJzIGluIGEgd2hvbGUgZ2Vub21lLiBFc3BlY2lhbGx5IHdlIGFyZSBpbnRlbmRlZCBpbiBmaW5kaW5nICZsZHF1bztjb21wb3NpdGlvbmFsbHkgZXF1aXZhbGVudCZyZHF1bzsgc3Vic3RyaW5ncy4gQSBzdHJpbmcgUCBpcyBzYWlkIHRvIGJlIGNvbXBvc2l0aW9uYWxseSBlcXVpdmFsZW50IHRvIGEgc3RyaW5nIFEgaWYgdGhlIG51bWJlciBvZiA0IGxldHRlcnMge0EsRyxULEN9IGFwcGVhcmluZyBpbiBQIGFuZCBRIGlzIGV4YWN0bHkgdGhlIHNhbWUuIEZvciBleGFtcGxlLCBQPSZsZHF1bztBVFRBVEdDJnJkcXVvOyBpcyBjb21wb3NpdGlvbmFsbHkgZXF1aXZhbGVudCB0byBRPSZsZHF1bztHVEFUQ1RBJnJkcXVvOyBzaW5jZSB0aGUgbnVtYmVyIG9mICZsc3F1bztBJnJzcXVvOyAsICZsc3F1bztHJnJzcXVvOyAsICZsc3F1bztDJnJzcXVvOyBhbmQgJmxzcXVvO1QmcnNxdW87IGluIFAgaXMgZXhhY3RseSBzYW1lIHRvIHRoYXQgaW4gUSwgcmVzcGVjdGl2ZWx5LiBJbiB0aGUgb3RoZXIgaGFuZCwgJmxkcXVvO1RUR0NBJnJkcXVvOyBpcyBub3QgY29tcG9zaXRpb25hbGx5IGVxdWl2YWxlbnQgdG8gJmxkcXVvO1RHQ0NBJnJkcXVvOy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtIHdlIHdhbnQgdG8gZmluZCB0aGUgay1NYWpvciBDb21wb3NpdGlvbiBTdWJzdHJpbmcgKGstTUNTIGZvciBzaG9ydCkuIEZvciBhIGdlbm9tZSBzdHJpbmcgZ2l2ZW4sIGstTUNTIGlzIGRlZmluZWQgYXMgdGhlIG1vc3QgZnJlcXVlbnRseSBhcHBlYXJpbmcgc3Vic3RyaW5nIG9mIGxlbmd0aCBrIHVwIHRvIGNvbXBvc2l0aW9uYWxseSBlcXVpdmFsZW5jZS4gU2luY2UgdGhlIGstTUNTIGZvciBhIGdpdmVuIGlucHV0IGdlbm9tZSBpcyBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLCB0d28gb3IgbW9yZSBkaWZmZXJlbnQgay1NQ1MgY291bGQgYmUgcG9zc2libGUuIEluIHRoZSBmb2xsb3dpbmcsIGstc3Vic3RyaW5nIG1lYW5zIGEgc3Vic3RyaW5nIG9mIGxlbmd0aCBrLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MZXQgdXMgc2hvdyBvbmUgZXhhbXBsZS4gV2UgaGF2ZSBhIGdlbm9tZSBzdHJpbmcgVz0mbGRxdW87R0NBR0dBR0NHQ0NBR0cmcmRxdW87IHdpdGggbGVuZ3RoIDE0LiBUaGVyZSBhcmUgbWFueSBkaWZmZXJlbnQgY29tcG9zaXRpb25hbGx5IGVxdWl2YWxlbnQgMy1zdWJzdHJpbmdzIHN1Y2ggYXMgR0NBLCBDQUcsIEdHQSwgR0FHLCZoZWxsaXA7IENBRyBhbmQgQUdHLiBJbiBXIGl0IGlzIGVhc3kgdG8gZmluZCB0aGF0ICZsZHF1bztBR0cmcmRxdW87aXMgYSAzLU1DUyB3aGljaCBhcHBlYXJzIGZvdXIgdGltZXMgYXMgQUdHLCBHR0EsIEdBRyBhbmQgQUdHLCBzaW5jZSB0aGVyZSBpcyBubyBvdGhlciAzLXN1YnN0cmluZyAodXAgdG8gY29tcG9zaXRpb25hbGx5IGVxdWl2YWxlbmNlKSB3aGljaCBhcHBlYXJzIG1vcmUgdGhhbiA0IHRpbWVzIGluIFcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCB0aGUgaW5wdXQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSAoaW5wdXQgZ2Vub21lKSBzdGFydHMgd2l0aCB0aGUgdmFsdWUgayBmb3Igay1NQ1MgYW5kIHRoZSBnZW5vbWUgc3RyaW5nIFcsIHdoZXJlIDEgJmxlOyBrICZsZTsgNjAwLiBUaGUgbGVuZ3RoIG9mIHRoZSBpbnB1dCBnZW5vbWUgc3RyaW5nLCB8V3wsIGlzIGJvdW5kZWQgYnkgMTAgJmxlOyB8V3wgJmxlOyA2MDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdGhlIG51bWJlciBvZiBvY2N1cnJlbmNlIG9mIGEgay1NQ1MgYXBwZWFyaW5nIGluIGVhY2ggZ2Vub21lIHN0cmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2008 B번