루미 알고리즘

#1406실버Namnsdag

PO 2016 온라인 예선코딩출제 Oskar Werkelin Ahlin영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Your friend likes money. When your friend has a name day he or she gets money from their nice aunt, hence your friend really enjoys when they have a name day.

It happens to be your friend's name day today, and your friend is considering how they could avoid having to wait another whole year before it's time for name day again. You've been asked to help out.

Your friend is planning to replace exactly one letter in their name in order to have a name day as soon as possible again. Given a list of name days for the coming year, please help your friend decide how soon they can have a name day again. It's forbidden to add or erase characters, you may only replace exactly one character with exactly one other character.

If it's impossible to find a name that can be reached with the above listed allowed actions, your friend will simply have to wait a whole year.

Input

Input starts with a single string, the name of your friend. Then follows an integer N on one row, the number of days in the coming year. After that follows N strings, the name days for days in the coming year.

The N:th name will always be the name of your friend, since it's their name day today and hence also in exactly one year again. The names in the input consist solely of characters a-z, contain no spaces and are at most 10 characters long. All names for the coming year will be different.

Output

Output a single integer on a single line: the minimum number of days before it's time for name day again, if you help your friend cheat with their name.

Explanation of sample

In the first sample input your friend's name is anna. She can make the name anja by replacing the second n in her name with a j, and thus she has a name day two days earlier than expected. Thus the answer is 3. In the second sample input it's impossible to create another name using the above listed actions, so jan will have to wait a whole year, 3 days.

Scoring

Your solution will be tested on a number of test case groups. To get points for a group you have to solve all the test cases in that group.

GroupPointsLimitsOther
1531 ≤ N ≤ 50
2471 ≤ N ≤ 10000

예제

예제 1

입력
anna
5
peter
petra
anja
markus
anna
출력
3

예제 2

입력
jan
3
petra
bengt
jan
출력
3

예제 3

입력
anya
4
ana
hanya
enya
anya
출력
3

출처 표기

출처: Programmeringsolympiaden 2016년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.