시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1341 236 115 17.088%

문제

인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다.

이 때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA가 특정 문자열을 부분 문자열로 가진다면 그 질병에 걸릴 가능성이 높다는 것이다. 이러한 특정 문자열을 마커(marker)라 한다.

하지만 때때로 DNA 구조를 그대로 확인하는 것만으로는 질병과 관련된 마커를 확인할 수 없는 경우가 있다. 마커의 돌연변이 가능성 때문이다.

마커의 돌연변이는 아래와 같이 일어난다.

  • 먼저, 마커를 세 부분으로 나눈다, 이 때, 첫 부분과 세 번째 부분은 비어 있어도 된다.
  • 두 번째 부분을 뒤집는다.

예를 들어 마커가 AGGT라면 아래와 같은 여섯 가지 경우가 가능하다.

GAGT, GGAT, TGGA, AGGT, ATGG, AGTG

어떤 사람의 DNA 구조와 마커가 주어졌을 때, DNA 내에 마커가 돌연변이의 형태를 포함하여 몇 번 출현하는지 세는 프로그램을 작성하라.

단, 마커의 출현 위치는 서로 겹쳐도 된다. 예를 들어 DNA 구조가 ATGGAT이며 마커가 AGGT라면 답은 3이 된다. ATGG, TGGA, GGAT가 한 번씩 출현하기 때문이다.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄엔 두 개의 정수 n과 m이 주어진다. 이는 각각 DNA 문자열의 길이와 마커의 길이이다. (1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 100) 두 번째 줄엔 DNA 구조가 주어진다. 마지막 줄엔 마커가 주어진다.

모든 DNA와 마커는 A,G,T,C로만 이루어진 문자열이다.

출력

각 테스트 케이스마다 주어진 DNA 구조에 마커와 그 돌연변이가 몇 번 출현하는지 하나의 정수로 출력한다.

만일 DNA 구조 내에 마커 또는 그 돌연변이가 한 번도 출현하지 않는다면 답은 0이 된다.

예제 입력 1

2
6 4
ATGGAT
AGGT
6 4
ATGGAT
AGCT

예제 출력 1

3
0

힌트

W3sicHJvYmxlbV9pZCI6IjEwMjU2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzhcdWFjMDRcdWM3NTggRE5BIFx1YWQ2Y1x1Yzg3MFx1YjI5NCBBLCBDLCBHLCBUXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ1NThcdWIwOThcdWM3NTggXHVhZTM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0YywgXHViYTg3IFx1YmE4NyBcdWM5YzhcdWJjZDFcdWM3NDAgRE5BIFx1YWQ2Y1x1Yzg3MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzViNFx1YjVhNCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YWNmYyBcdWFkMDBcdWI4MjhcdWM3NzQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJjMWRcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM3N2MgRE5BXHVhYzAwIFx1ZDJiOVx1YzgxNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWFjMDBcdWM5YzRcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YzljOFx1YmNkMVx1YzVkMCBcdWFjNzhcdWI5YjQgXHVhYzAwXHViMmE1XHVjMTMxXHVjNzc0IFx1YjE5Mlx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQyYjlcdWM4MTUgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljOFx1Y2VlNChtYXJrZXIpXHViNzdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YjU0Y1x1YjU0Y1x1Yjg1YyBETkEgXHVhZDZjXHVjODcwXHViOTdjIFx1YWRmOFx1YjMwMFx1Yjg1YyBcdWQ2NTVcdWM3NzhcdWQ1NThcdWIyOTQgXHVhYzgzXHViOWNjXHVjNzNjXHViODVjXHViMjk0IFx1YzljOFx1YmNkMVx1YWNmYyBcdWFkMDBcdWI4MjhcdWI0MWMgXHViOWM4XHVjZWU0XHViOTdjIFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjljOFx1Y2VlNFx1Yzc1OCBcdWIzY2NcdWM1ZjBcdWJjYzBcdWM3NzQgXHVhYzAwXHViMmE1XHVjMTMxIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjZWU0XHVjNzU4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAsIFx1YjljOFx1Y2VlNFx1Yjk3YyBcdWMxMzggXHViZDgwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOFx1YjJlNCwgXHVjNzc0IFx1YjU0YywgXHVjY2FiIFx1YmQ4MFx1YmQ4NFx1YWNmYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YmQ4MFx1YmQ4NFx1Yzc0MCBcdWJlNDRcdWM1YjQgXHVjNzg4XHVjNWI0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWJkODBcdWJkODRcdWM3NDQgXHViNGE0XHVjOWQxXHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViOWM4XHVjZWU0XHVhYzAwIEFHR1RcdWI3N2NcdWJhNzQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM1ZWNcdWMxMmYgXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkdBR1QsIEdHQVQsIFRHR0EsIEFHR1QsIEFUR0csIEFHVEc8XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBETkEgXHVhZDZjXHVjODcwXHVjNjQwIFx1YjljOFx1Y2VlNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBETkEgXHViMGI0XHVjNWQwIFx1YjljOFx1Y2VlNFx1YWMwMCBcdWIzY2NcdWM1ZjBcdWJjYzBcdWM3NzRcdWM3NTggXHVkNjE1XHVkMGRjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYyBcdWJhODcgXHViYzg4IFx1Y2Q5Y1x1ZDYwNFx1ZDU1OFx1YjI5NFx1YzljMCBcdWMxMzhcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHViMmU4LCBcdWI5YzhcdWNlZTRcdWM3NTggXHVjZDljXHVkNjA0IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVhY2I5XHVjY2QwXHViM2M0IFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBETkEgXHVhZDZjXHVjODcwXHVhYzAwIEFUR0dBVFx1Yzc3NFx1YmE3MCBcdWI5YzhcdWNlZTRcdWFjMDAgQUdHVFx1Yjc3Y1x1YmE3NCBcdWIyZjVcdWM3NDAgM1x1Yzc3NCBcdWI0MWNcdWIyZTQuIEFUR0csIFRHR0EsIEdHQVRcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWNkOWNcdWQ2MDRcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIEROQSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YjljOFx1Y2VlNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCwgMSAmbGU7IG0gJmxlOyAxMDApJm5ic3A7PFwvc3Bhbj48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDQgRE5BIFx1YWQ2Y1x1Yzg3MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvc3Bhbj48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkNCBcdWI5YzhcdWNlZTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3NwYW4+PFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBETkFcdWM2NDAgXHViOWM4XHVjZWU0XHViMjk0IEEsRyxULENcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM4ZmNcdWM1YjRcdWM5YzQgRE5BIFx1YWQ2Y1x1Yzg3MFx1YzVkMCBcdWI5YzhcdWNlZTRcdWM2NDAgXHVhZGY4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1YWMwMCBcdWJhODcgXHViYzg4IFx1Y2Q5Y1x1ZDYwNFx1ZDU1OFx1YjI5NFx1YzljMCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNzdjIEROQSBcdWFkNmNcdWM4NzAgXHViMGI0XHVjNWQwIFx1YjljOFx1Y2VlNCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NFx1YWMwMCBcdWQ1NWMgXHViYzg4XHViM2M0IFx1Y2Q5Y1x1ZDYwNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgXHViMmY1XHVjNzQwIDBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMjU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTXV0YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBodW1hbiBETkEgc2VxdWVuY2UgY2FuIGJlIGNvbnNpZGVyZWQgYXMgYSBsb25nIHN0cmluZyBtYWRlIHVwIHdpdGggZm91ciBsZXR0ZXJzLCBBLCBHLCBULCBhbmQgQy4gSXQgaXMga25vd24gdGhhdCBzb21lIGRpc2Vhc2VzIGFyZSByZWxhdGVkIHRvIGEgbWFya2VyLCBhIHNob3J0IHN1YnN0cmluZyBvZiB0aGUgRE5BIHNlcXVlbmNlLiBJZiB5b3VyIEROQSBjb250YWlucyBpdCwgdGhlbiBpdCBpcyBsaWtlbHkgdGhhdCB5b3UgaGF2ZSBhIGhpZ2hlciBwcm9iYWJpbGl0eSBvZiBzdWZmZXJpbmcgZnJvbSB0aG9zZSBkaXNlYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U29tZXRpbWVzIGl0IGlzIG5vdCBlbm91Z2ggdG8gZmluZCBtYXJrZXJzIGZyb20geW91ciBETkEgc2VxdWVuY2VzLiBNdXRhdGlvbiBjYW4gY2hhbmdlIHRoZSBtYXJrZXIuIFRoYXQgaXMsIHRoZSBtYXJrZXIgY2FuIGJlIGRpdmlkZWQgaW50byB0aHJlZSBwYXJ0cyBhbmQgdGhlIG1pZGRsZSBvbmUgY2FuIGJlIHJldmVyc2VkLiBOb3RlIHRoYXQgdGhlIGZpcnN0IG9yIHRoZSB0aGlyZCBvbmUgY2FuIGJlIGFuIGVtcHR5IHN0cmluZy4gRm9yIGV4YW1wbGUsIGlmIHRoZSBtYXJrZXIgaXMgQUdHVCwgY29uc2lkZXJpbmcgdGhlIG11dGF0aW9uLCB0aGVyZSBjYW4gYmUgc2l4IGNhc2VzOiBHQUdULCBHR0FULCBUR0dBLCBBR0dULCBBVEdHLCBhbmQgQUdURy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4geW91ciBETkEgc2VxdWVuY2UgYW5kIHRoZSBtYXJrZXIsIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBjb21wdXRlcyB0aGUgbnVtYmVyIG9mIG9jY3VycmVuY2VzIG9mIHRoZSBtYXJrZXIgb3IgaXRzIG11dGF0aW9ucy4gRm9yIGV4YW1wbGUsIGlmIHlvdXIgRE5BIHNlcXVlbmNlIGlzIEFUR0dBVCBhbmQgdGhlIG1hcmtlciBpcyBBR0dUIGFnYWluLCB0aGUgYW5zd2VyIGlzIDMgYXMgaXQgaW5jbHVkZXMgQVRHRywgVEdHQSwgYW5kIEdHQVQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGludGVnZXJzIG4gYW5kIG0sIHRoZSBsZW5ndGggb2YgeW91ciBETkEgc2VxdWVuY2UgYW5kIHRoYXQgb2YgdGhlIG1hcmtlciwgcmVzcGVjdGl2ZWx5LCB3aGVyZSAxICZsZTsgbiAmbGU7IDEsIDAwMCwgMDAwIGFuZCAxICZsZTsgbSAmbGU7IDEwMC4gVGhlIHNlY29uZCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIHlvdXIgRE5BIHNlcXVlbmNlLiBUaGUgdGhpcmQgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0aGUgbWFya2VyLiBBbGwgdGhlIHN0cmluZ3MgYXJlIG1hZGUgdXAgd2l0aCBmb3VyIGxldHRlcnMsIEEsIEcsIFQsIGFuZCBDLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBudW1iZXIgb2Ygb2NjdXJyZW5jZXMgb2YgdGhlIG1hcmtlciBhbmQgaXRzIG11dGF0ZWQgc3RyaW5ncyBpbiB5b3VyIEROQSBzZXF1ZW5jZS4gSWYgdGhlcmUgaXMgbm8gc3VjaCBvY2N1cnJlbmNlLCBwcmludCAwLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==