시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 682 371 328 57.951%

문제

당신은 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 개가 된다.

W3sicHJvYmxlbV9pZCI6IjU1NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMThcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBOIFx1YWMxY1x1Yzc1OCBcdWJjMThcdWM5YzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzE4XHVjOWMwXHViMjk0Jm5ic3A7XHViMzAwXHViYjM4XHVjNzkwIDEwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzBjOFx1YWNhOFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHViYzE4XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWFjZmMgXHViMDVkXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzBjOFx1YWNhOFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHViYzE4XHVjOWMwXHVjNWQwIFx1YWMwMVx1Yzc3OFx1YjQxYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVhYzcwXHVhZmI4XHViODVjIFx1Yzc3ZFx1YjI5NCBcdWFjNzFcdWM4MTVcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjM2VcdWFjZTBcdWM3OTBcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVhZGY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHViYzE4XHVjOWMwXHVhYzAwIFx1YmE4NyBcdWFjMWNcdWM3NzhcdWM5YzBcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgMiArIE4gXHVkNTg5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAxIFx1Yzc5MCBcdWM3NzRcdWMwYzEgMTAgXHVjNzkwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIFx1Y2MzZVx1YWNlMFx1Yzc5MFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMThcdWM5YzBcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgXHUyMjY2IE4gXHUyMjY2IDEwMClcdWM3NzQgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4yK2kmbmJzcDtcdWM5MDQoMSBcdTIyNjYgaSBcdTIyNjYgTilcdWM1ZDQmbmJzcDtpXHVhYzFjXHVjNzU4IFx1YmMxOFx1YzljMFx1YzVkMCBcdWMwYzhcdWFjYThcdWM4MzhcdWM3ODhcdWFjZTAsJm5ic3A7MTAgXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2MzZVx1YWNlMFx1Yzc5MFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVkM2VjXHVkNTY4IFx1YmMxOFx1YzljMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+Jmx0O1x1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjUmbmJzcDsyJmd0O1x1Yzc1OCBcdWJjMThcdWM5YzBcdWM1ZDBcdWIyOTQgJnF1b3Q7WFlaJnF1b3Q7XHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LiBcdWM3NzRcdWFjODNcdWM3NDAgXHViYzE4XHVjOWMwXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWFjZmMgXHViMDVkXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mbHQ7XHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNSAzJmd0O1x1Yzc1OCBcdWNjYWImbmJzcDtcdWJjODhcdWM5ZjggXHViYzE4XHVjOWMwXHViMjk0ICZxdW90O1BRUiZxdW90O1x1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgMiBcdWFjMWMgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJjMThcdWM5YzBcdWIyOTQgJnF1b3Q7UFFSJnF1b3Q7XHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAxIFx1YWMxYyBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCZuYnNwO1x1YzEzOCBcdWJjODhcdWM5ZjggXHViYzE4XHVjOWMwXHVjNWQwXHViMjk0ICZxdW90O1BRUiZxdW90O1x1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyAmcXVvdDtQUVImcXVvdDtcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWJjMThcdWM5YzBcdWM3NTggXHVjMjE4XHViMjk0IDIgXHVhYzFjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1NTUiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJcdTYzMDdcdThmMmEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZiBOIFx1NTAwYlx1MzA2ZVx1NjMwN1x1OGYyYVx1MzA5Mlx1NjMwMVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTMwNjlcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwODJcdWZmMGNcdTMwYTJcdTMwZWJcdTMwZDVcdTMwYTFcdTMwZDlcdTMwYzNcdTMwYzhcdTMwNmVcdTU5MjdcdTY1ODdcdTViNTcgMTAgXHU2NTg3XHU1YjU3XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU1MjNiXHU1MzcwXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1NjMwN1x1OGYyYVx1MzA2Ylx1MzA2Zlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1NjcwMFx1NTIxZFx1MzA2OFx1NjcwMFx1NWY4Y1x1MzA0Y1x1MzA2NFx1MzA2YVx1MzA0Y1x1MzA2M1x1MzA1Zlx1NWY2Mlx1MzA2N1x1NjU4N1x1NWI1N1x1MzA0Y1x1NTIzYlx1NTM3MFx1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTYzMDdcdThmMmFcdTMwNmJcdTUyM2JcdTUzNzBcdTMwNTVcdTMwOGNcdTMwNWZcdTY1ODdcdTViNTdcdTUyMTdcdTMwOTJcdTkwMDZcdTk4MDZcdTMwNmJcdThhYWRcdTMwODBcdTVmYzNcdTkxNGRcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU2M2EyXHUzMDU3XHUzMDVmXHUzMDQ0XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjXHUzMDVkXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyXHU1NDJiXHUzMDgwXHU2MzA3XHU4ZjJhXHUzMDRjXHU0ZjU1XHU1MDBiXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmYgMitOIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1ZmYwYzEgXHU2NTg3XHU1YjU3XHU0ZWU1XHU0ZTBhIDEwIFx1NjU4N1x1NWI1N1x1NGVlNVx1NGUwYlx1MzA2ZVx1MzBhMlx1MzBlYlx1MzBkNVx1MzBhMVx1MzBkOVx1MzBjM1x1MzBjOFx1MzA2ZVx1NTkyN1x1NjU4N1x1NWI1N1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1NjNhMlx1MzA1N1x1MzA1Zlx1MzA0NFx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4yIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NjMwN1x1OGYyYVx1MzA2ZVx1NTAwYlx1NjU3MCBOICggMSBcdTIyNjYgTiBcdTIyNjYgMTAwIClcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MitpIFx1ODg0Y1x1NzZlZSgxIFx1MjI2NiBpIFx1MjI2NiBOIClcdTMwNmJcdTMwNmZcdWZmMGMgaSBcdTUwMGJcdTc2ZWVcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTUyM2JcdTUzNzBcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGIgMTAgXHU2NTg3XHU1YjU3XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU2M2EyXHUzMDU3XHUzMDVmXHUzMDQ0XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyXHU1NDJiXHUzMDgwXHU2MzA3XHU4ZjJhXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbiIsImhpbnQiOiI8cD5cdTUxNjVcdTUyOWJcdTRmOGIgMiBcdTMwNmVcdTYzMDdcdThmMmFcdTMwNmJcdTMwNmZcdTMwMGNYWVpcdTMwMGRcdTMwNjhcdTMwNDRcdTMwNDZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGMgMSBcdTMwNjRcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdTMwMDFcdTYzMDdcdThmMmFcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmVcdTY3MDBcdTUyMWRcdTMwNjhcdTY3MDBcdTVmOGNcdTMwNGNcdTMwNjRcdTMwNmFcdTMwNGNcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNWZcdTMwODFcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1MTY1XHU1MjliXHU0ZjhiIDMgXHUzMDZlIDEgXHU1MDBiXHU3NmVlXHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDZiXHUzMDZmXHUzMDBjUFFSXHUzMDBkXHUzMDY4XHUzMDQ0XHUzMDQ2XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjIDIgXHUzMDY0XHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDRhXHUzMDhhXHVmZjBjIDIgXHU1MDBiXHU3NmVlXHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDZiXHUzMDZmXHUzMDBjUFFSXHUzMDBkXHUzMDY4XHUzMDQ0XHUzMDQ2XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjIDEgXHU1MDBiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDRhXHUzMDhhXHVmZjBjIDMgXHU1MDBiXHU3NmVlXHUzMDZlXHU2MzA3XHU4ZjJhXHUzMDZiXHUzMDZmXHUzMDBjUFFSXHUzMDBkXHUzMDY4XHUzMDQ0XHUzMDQ2XHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDZhXHUzMDQ0XHVmZjBlIFx1MzA1ZFx1MzA2ZVx1MzA1Zlx1MzA4MVx1MzAwY1BRUlx1MzAwZFx1MzA2OFx1MzA0NFx1MzA0Nlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1NjMwN1x1OGYyYVx1MzA2ZVx1NjU3MFx1MzA2ZiAyIFx1NTAwYlx1MzA2OFx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTIwM2JcdTU0MDRcdTUxNjVcdTUxZmFcdTUyOWJcdTRmOGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwNmZcdWZmMGMgXHU1M2YzXHUzMGFmXHUzMGVhXHUzMGMzXHUzMGFmXHU3YjQ5XHUzMDZiXHUzMDg4XHUzMDhhXHUzMGQ1XHUzMGExXHUzMGE0XHUzMGViXHUzMDZiXHU0ZmRkXHU1YjU4XHUzMDU3XHUzMDY2XHU1MjI5XHU3NTI4XHU1M2VmXHU4MGZkXHUzMDY3XHUzMDU5XHVmZjBlPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=

출처

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