시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1601 302 150 17.668%

문제

인간의 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+XHVjNzc0XHViNTRjLCBcdWJhODcgXHViYTg3IFx1YzljOFx1YmNkMVx1Yzc0MCBETkEgXHVhZDZjXHVjODcwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjNWI0XHViNWE0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVhY2ZjIFx1YWQwMFx1YjgyOFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmMxZFx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1Yzc3YyBETkFcdWFjMDAgXHVkMmI5XHVjODE1IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YWMwMFx1YzljNFx1YjJlNFx1YmE3NCBcdWFkZjggXHVjOWM4XHViY2QxXHVjNWQwIFx1YWM3OFx1YjliNCBcdWFjMDBcdWIyYTVcdWMxMzFcdWM3NzQgXHViMTkyXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1ZDJiOVx1YzgxNSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWM4XHVjZWU0KG1hcmtlcilcdWI3N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHViNTRjXHViNTRjXHViODVjIEROQSBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhZGY4XHViMzAwXHViODVjIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YjI5NCBcdWFjODNcdWI5Y2NcdWM3M2NcdWI4NWNcdWIyOTQgXHVjOWM4XHViY2QxXHVhY2ZjIFx1YWQwMFx1YjgyOFx1YjQxYyBcdWI5YzhcdWNlZTRcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjZWU0XHVjNzU4IFx1YjNjY1x1YzVmMFx1YmNjMFx1Yzc3NCBcdWFjMDBcdWIyYTVcdWMxMzEgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWNlZTRcdWM3NTggXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YmEzY1x1YzgwMCwgXHViOWM4XHVjZWU0XHViOTdjIFx1YzEzOCBcdWJkODBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4XHViMmU0LCBcdWM3NzRcdWI1NGMsIFx1Y2NhYiBcdWJkODBcdWJkODRcdWFjZmMgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWJkODBcdWJkODRcdWM3NDAgXHViZTQ0XHVjNWI0IFx1Yzc4OFx1YzViNFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHViZDgwXHViZDg0XHVjNzQ0IFx1YjRhNFx1YzlkMVx1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjljOFx1Y2VlNFx1YWMwMCBBR0dUXHViNzdjXHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNWVjXHVjMTJmIFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5HQUdULCBHR0FULCBUR0dBLCBBR0dULCBBVEdHLCBBR1RHPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWMwYWNcdWI3OGNcdWM3NTggRE5BIFx1YWQ2Y1x1Yzg3MFx1YzY0MCBcdWI5YzhcdWNlZTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgRE5BIFx1YjBiNFx1YzVkMCBcdWI5YzhcdWNlZTRcdWFjMDAgXHViM2NjXHVjNWYwXHViY2MwXHVjNzc0XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM1ZWMgXHViYTg3IFx1YmM4OCBcdWNkOWNcdWQ2MDRcdWQ1NThcdWIyOTRcdWM5YzAgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCwgXHViOWM4XHVjZWU0XHVjNzU4IFx1Y2Q5Y1x1ZDYwNCBcdWM3MDRcdWNlNThcdWIyOTQgXHVjMTFjXHViODVjIFx1YWNiOVx1Y2NkMFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgRE5BIFx1YWQ2Y1x1Yzg3MFx1YWMwMCBBVEdHQVRcdWM3NzRcdWJhNzAgXHViOWM4XHVjZWU0XHVhYzAwIEFHR1RcdWI3N2NcdWJhNzQgXHViMmY1XHVjNzQwIDNcdWM3NzQgXHViNDFjXHViMmU0LiBBVEdHLCBUR0dBLCBHR0FUXHVhYzAwIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHVjZDljXHVkNjA0XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggblx1YWNmYyBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHVjNzc0XHViMjk0IFx1YWMwMVx1YWMwMSBETkEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWI5YzhcdWNlZTRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxLDAwMCwwMDAsIDEgJmxlOyBtICZsZTsgMTAwKSZuYnNwOzxcL3NwYW4+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQ0IEROQSBcdWFkNmNcdWM4NzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3NwYW4+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDQgXHViOWM4XHVjZWU0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9zcGFuPjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgRE5BXHVjNjQwIFx1YjljOFx1Y2VlNFx1YjI5NCBBLEcsVCxDXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjOGZjXHVjNWI0XHVjOWM0IEROQSBcdWFkNmNcdWM4NzBcdWM1ZDAgXHViOWM4XHVjZWU0XHVjNjQwIFx1YWRmOCBcdWIzY2NcdWM1ZjBcdWJjYzBcdWM3NzRcdWFjMDAgXHViYTg3IFx1YmM4OCBcdWNkOWNcdWQ2MDRcdWQ1NThcdWIyOTRcdWM5YzAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1Yzc3YyBETkEgXHVhZDZjXHVjODcwIFx1YjBiNFx1YzVkMCBcdWI5YzhcdWNlZTQgXHViNjEwXHViMjk0IFx1YWRmOCBcdWIzY2NcdWM1ZjBcdWJjYzBcdWM3NzRcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YjNjNCBcdWNkOWNcdWQ2MDRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1YjJmNVx1Yzc0MCAwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDI1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11dGF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgaHVtYW4gRE5BIHNlcXVlbmNlIGNhbiBiZSBjb25zaWRlcmVkIGFzIGEgbG9uZyBzdHJpbmcgbWFkZSB1cCB3aXRoIGZvdXIgbGV0dGVycywgQSwgRywgVCwgYW5kIEMuIEl0IGlzIGtub3duIHRoYXQgc29tZSBkaXNlYXNlcyBhcmUgcmVsYXRlZCB0byBhIG1hcmtlciwgYSBzaG9ydCBzdWJzdHJpbmcgb2YgdGhlIEROQSBzZXF1ZW5jZS4gSWYgeW91ciBETkEgY29udGFpbnMgaXQsIHRoZW4gaXQgaXMgbGlrZWx5IHRoYXQgeW91IGhhdmUgYSBoaWdoZXIgcHJvYmFiaWxpdHkgb2Ygc3VmZmVyaW5nIGZyb20gdGhvc2UgZGlzZWFzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvbWV0aW1lcyBpdCBpcyBub3QgZW5vdWdoIHRvIGZpbmQgbWFya2VycyBmcm9tIHlvdXIgRE5BIHNlcXVlbmNlcy4gTXV0YXRpb24gY2FuIGNoYW5nZSB0aGUgbWFya2VyLiBUaGF0IGlzLCB0aGUgbWFya2VyIGNhbiBiZSBkaXZpZGVkIGludG8gdGhyZWUgcGFydHMgYW5kIHRoZSBtaWRkbGUgb25lIGNhbiBiZSByZXZlcnNlZC4gTm90ZSB0aGF0IHRoZSBmaXJzdCBvciB0aGUgdGhpcmQgb25lIGNhbiBiZSBhbiBlbXB0eSBzdHJpbmcuIEZvciBleGFtcGxlLCBpZiB0aGUgbWFya2VyIGlzIEFHR1QsIGNvbnNpZGVyaW5nIHRoZSBtdXRhdGlvbiwgdGhlcmUgY2FuIGJlIHNpeCBjYXNlczogR0FHVCwgR0dBVCwgVEdHQSwgQUdHVCwgQVRHRywgYW5kIEFHVEcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHlvdXIgRE5BIHNlcXVlbmNlIGFuZCB0aGUgbWFya2VyLCB3cml0ZSBhIHByb2dyYW0gd2hpY2ggY29tcHV0ZXMgdGhlIG51bWJlciBvZiBvY2N1cnJlbmNlcyBvZiB0aGUgbWFya2VyIG9yIGl0cyBtdXRhdGlvbnMuIEZvciBleGFtcGxlLCBpZiB5b3VyIEROQSBzZXF1ZW5jZSBpcyBBVEdHQVQgYW5kIHRoZSBtYXJrZXIgaXMgQUdHVCBhZ2FpbiwgdGhlIGFuc3dlciBpcyAzIGFzIGl0IGluY2x1ZGVzIEFUR0csIFRHR0EsIGFuZCBHR0FULiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBpbnRlZ2VycyBuIGFuZCBtLCB0aGUgbGVuZ3RoIG9mIHlvdXIgRE5BIHNlcXVlbmNlIGFuZCB0aGF0IG9mIHRoZSBtYXJrZXIsIHJlc3BlY3RpdmVseSwgd2hlcmUgMSAmbGU7IG4gJmxlOyAxLCAwMDAsIDAwMCBhbmQgMSAmbGU7IG0gJmxlOyAxMDAuIFRoZSBzZWNvbmQgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB5b3VyIEROQSBzZXF1ZW5jZS4gVGhlIHRoaXJkIGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgdGhlIG1hcmtlci4gQWxsIHRoZSBzdHJpbmdzIGFyZSBtYWRlIHVwIHdpdGggZm91ciBsZXR0ZXJzLCBBLCBHLCBULCBhbmQgQy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYW4gaW50ZWdlciB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIG9jY3VycmVuY2VzIG9mIHRoZSBtYXJrZXIgYW5kIGl0cyBtdXRhdGVkIHN0cmluZ3MgaW4geW91ciBETkEgc2VxdWVuY2UuIElmIHRoZXJlIGlzIG5vIHN1Y2ggb2NjdXJyZW5jZSwgcHJpbnQgMC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=