시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 784 439 384 59.168%

문제

당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 거꾸로 읽는 걱정은 없다.

찾고자하는 문자열이 주어졌을 때 그 문자열을 포함하는 반지가 몇 개인지를 발견하는 프로그램을 작성하라.

입력

입력은 총 2 + N 줄 이다.

첫 번째 줄에는 1 자 이상 10 자 이하의 대문자로 구성된 찾고자 하는 문자열이 적혀있다.

두 번째 줄에는 반지의 개수 N (1 ≦ N ≦ 100)이 적혀있다.

2+i 줄(1 ≦ i ≦ N)엔 i개의 반지에 새겨져있고, 10 문자로 이루어진 문자열이 적혀있다.

출력

찾고자하는 문자열을 포함 반지의 개수를 나타내는 정수를 한 줄로 출력하라.

예제 입력 1

ABCD
3
ABCDXXXXXX
YYYYABCDXX
DCBAZZZZZZ

예제 출력 1

2

예제 입력 2

XYZ
1
ZAAAAAAAXY

예제 출력 2

1

예제 입력 3

PQR
3
PQRAAAAPQR
BBPQRBBBBB
CCCCCCCCCC

예제 출력 3

2

힌트

<예제 입력 2>의 반지에는 "XYZ"라는 문자열이 하나 포함되어있다. 이것은 반지의 문자열의 시작과 끝이 연결되어 있기 때문이다.

<예제 입력 3>의 첫 번째 반지는 "PQR"이라는 단어가 2 개 포함되어 있으며, 두 번째 반지는 "PQR"라는 문자열이 1 개 포함되어 있으며, 세 번째 반지에는 "PQR"라는 문자열이 포함되어 있지 않다. 따라서 "PQR"라는 문자열이 포함되어있는 반지의 수는 2 개가 된다.

W3sicHJvYmxlbV9pZCI6IjU1NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMThcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzE4XHVjOWMwXHViMjk0Jm5ic3A7XHViMzAwXHViYjM4XHVjNzkwIDEwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzBjOFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmMxOFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMmRjXHVjNzkxXHVhY2ZjIFx1YjA1ZFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkNjE1XHVkMGRjXHViODVjIFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWMwYzhcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJjMThcdWM5YzBcdWM1ZDAgXHVhYzAxXHVjNzc4XHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWFjNzBcdWFmYjhcdWI4NWMgXHVjNzdkXHViMjk0IFx1YWM3MVx1YzgxNVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZVx1YWNlMFx1Yzc5MFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWFkZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWJjMThcdWM5YzBcdWFjMDAgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkMWQgMiArIE4gXHVjOTA0IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMSBcdWM3OTAgXHVjNzc0XHVjMGMxIDEwIFx1Yzc5MCBcdWM3NzRcdWQ1NThcdWM3NTggXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWNjM2VcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxOFx1YzljMFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMSBcdTIyNjYgTiBcdTIyNjYgMTAwKVx1Yzc3NCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjIraSZuYnNwO1x1YzkwNCgxIFx1MjI2NiBpIFx1MjI2NiBOKVx1YzVkNCZuYnNwO2lcdWFjMWNcdWM3NTggXHViYzE4XHVjOWMwXHVjNWQwIFx1YzBjOFx1YWNhOFx1YzgzOFx1Yzc4OFx1YWNlMCwmbmJzcDsxMCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjYzNlXHVhY2UwXHVjNzkwXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQzZWNcdWQ1NjggXHViYzE4XHVjOWMwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4mbHQ7XHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNSZuYnNwOzImZ3Q7XHVjNzU4IFx1YmMxOFx1YzljMFx1YzVkMFx1YjI5NCAmcXVvdDtYWVomcXVvdDtcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWJjMThcdWM5YzBcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzJkY1x1Yzc5MVx1YWNmYyBcdWIwNWRcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZsdDtcdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1IDMmZ3Q7XHVjNzU4IFx1Y2NhYiZuYnNwO1x1YmM4OFx1YzlmOCBcdWJjMThcdWM5YzBcdWIyOTQgJnF1b3Q7UFFSJnF1b3Q7XHVjNzc0XHViNzdjXHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCAyIFx1YWMxYyBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmMxOFx1YzljMFx1YjI5NCAmcXVvdDtQUVImcXVvdDtcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IDEgXHVhYzFjIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsJm5ic3A7XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWJjMThcdWM5YzBcdWM1ZDBcdWIyOTQgJnF1b3Q7UFFSJnF1b3Q7XHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjICZxdW90O1BRUiZxdW90O1x1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YmMxOFx1YzljMFx1Yzc1OCBcdWMyMThcdWIyOTQgMiBcdWFjMWNcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTU1NSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1NjMwN1x1OGYyYSIsImRlc2NyaXB0aW9uIjoiPHA+XHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZmIE4gXHU1MDBiXHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDkyXHU2MzAxXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1MzA2OVx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA4Mlx1ZmYwY1x1MzBhMlx1MzBlYlx1MzBkNVx1MzBhMVx1MzBkOVx1MzBjM1x1MzBjOFx1MzA2ZVx1NTkyN1x1NjU4N1x1NWI1NyAxMCBcdTY1ODdcdTViNTdcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTUyM2JcdTUzNzBcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHU2MzA3XHU4ZjJhXHUzMDZiXHUzMDZmXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHU2NzAwXHU1MjFkXHUzMDY4XHU2NzAwXHU1ZjhjXHUzMDRjXHUzMDY0XHUzMDZhXHUzMDRjXHUzMDYzXHUzMDVmXHU1ZjYyXHUzMDY3XHU2NTg3XHU1YjU3XHUzMDRjXHU1MjNiXHU1MzcwXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1NjMwN1x1OGYyYVx1MzA2Ylx1NTIzYlx1NTM3MFx1MzA1NVx1MzA4Y1x1MzA1Zlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA5Mlx1OTAwNlx1OTgwNlx1MzA2Ylx1OGFhZFx1MzA4MFx1NWZjM1x1OTE0ZFx1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTYzYTJcdTMwNTdcdTMwNWZcdTMwNDRcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNcdTMwNWRcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwOTJcdTU0MmJcdTMwODBcdTYzMDdcdThmMmFcdTMwNGNcdTRmNTVcdTUwMGJcdTMwNDJcdTMwOGJcdTMwNGJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzA2ZiAyK04gXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHVmZjBjMSBcdTY1ODdcdTViNTdcdTRlZTVcdTRlMGEgMTAgXHU2NTg3XHU1YjU3XHU0ZWU1XHU0ZTBiXHUzMDZlXHUzMGEyXHUzMGViXHUzMGQ1XHUzMGExXHUzMGQ5XHUzMGMzXHUzMGM4XHUzMDZlXHU1OTI3XHU2NTg3XHU1YjU3XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2M2EyXHUzMDU3XHUzMDVmXHUzMDQ0XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHVmZjBjXHU2MzA3XHU4ZjJhXHUzMDZlXHU1MDBiXHU2NTcwIE4gKCAxIFx1MjI2NiBOIFx1MjI2NiAxMDAgKVx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4yK2kgXHU4ODRjXHU3NmVlKDEgXHUyMjY2IGkgXHUyMjY2IE4gKVx1MzA2Ylx1MzA2Zlx1ZmYwYyBpIFx1NTAwYlx1NzZlZVx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1NTIzYlx1NTM3MFx1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4YiAxMCBcdTY1ODdcdTViNTdcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTYzYTJcdTMwNTdcdTMwNWZcdTMwNDRcdTY1ODdcdTViNTdcdTUyMTdcdTMwOTJcdTU0MmJcdTMwODBcdTYzMDdcdThmMmFcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG5cclxuIiwiaGludCI6IjxwPlx1NTE2NVx1NTI5Ylx1NGY4YiAyIFx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1MzAwY1hZWlx1MzAwZFx1MzA2OFx1MzA0NFx1MzA0Nlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0YyAxIFx1MzA2NFx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1MzAwMVx1NjMwN1x1OGYyYVx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1NjcwMFx1NTIxZFx1MzA2OFx1NjcwMFx1NWY4Y1x1MzA0Y1x1MzA2NFx1MzA2YVx1MzA0Y1x1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTUxNjVcdTUyOWJcdTRmOGIgMyBcdTMwNmUgMSBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGMgMiBcdTMwNjRcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGMgMiBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGMgMSBcdTUwMGJcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGMgMyBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNQUVJcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwNmFcdTMwNDRcdWZmMGUgXHUzMDVkXHUzMDZlXHUzMDVmXHUzMDgxXHUzMDBjUFFSXHUzMDBkXHUzMDY4XHUzMDQ0XHUzMDQ2XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU2MzA3XHU4ZjJhXHUzMDZlXHU2NTcwXHUzMDZmIDIgXHU1MDBiXHUzMDY4XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MjAzYlx1NTQwNFx1NTE2NVx1NTFmYVx1NTI5Ylx1NGY4Ylx1MzA2ZVx1MzBjN1x1MzBmY1x1MzBiZlx1MzA2Zlx1ZmYwYyBcdTUzZjNcdTMwYWZcdTMwZWFcdTMwYzNcdTMwYWZcdTdiNDlcdTMwNmJcdTMwODhcdTMwOGFcdTMwZDVcdTMwYTFcdTMwYTRcdTMwZWJcdTMwNmJcdTRmZGRcdTViNThcdTMwNTdcdTMwNjZcdTUyMjlcdTc1MjhcdTUzZWZcdTgwZmRcdTMwNjdcdTMwNTlcdWZmMGU8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==

출처

Olympiad > 일본정보올림피아드 예선 > JOI 2011 예선 2번