Baza

두 단어의 최장 공통 접두사는 두 단어가 모두 그것으로 시작하는 가장 긴 단어이다. 예를 들어 단어 identity와 idealistic의 최장 공통 접두사는 단어 ide이다.

어떤 데이터베이스에 \(N\)개의 단어가 들어 있다.

데이터베이스에서 질의 단어 \(W\)를 검색하는 알고리즘은 원시적이다. 단어 \(W\)를 데이터베이스의 각 단어와 하나씩 비교한다. 두 단어는 서로 다른 글자가 나오거나 한 단어의 끝에 도달할 때까지 글자 단위로 비교된다(그 시점에 두 단어가 같은지, 아니면 한 단어가 더 긴지가 판정된다). 알고리즘은 데이터베이스에서 단어 \(W\)를 찾으면 종료한다.

알고리즘을 분석해 보면, 단어 \(W\)를 찾는 데 필요한 단계 수는 \(W\)와 비교한 단어의 개수에, \(W\)와 비교한 각 단어와의 최장 공통 접두사 길이의 합을 더한 것과 같다.

\(Q\)개의 질의 단어 각각을 찾는 데 알고리즘이 사용하는 단계 수를 계산하는 프로그램을 작성하시오.

첫째 줄에 데이터베이스의 단어 개수인 정수 \(N\) (\(1 \le N \le 30\,000\))이 주어진다.

다음 \(N\)개의 줄에 데이터베이스의 단어가 하나씩 주어진다. 단어는 알고리즘이 질의 단어와 비교하는 순서대로 주어진다. 데이터베이스의 모든 단어는 서로 다르다.

다음 줄에 검색할 단어의 개수인 정수 \(Q\) (\(1 \le Q \le 30\,000\))가 주어진다.

다음 \(Q\)개의 줄에 질의 단어가 하나씩 주어진다.

입력의 모든 단어는 영어 알파벳 소문자 \(30\)자 미만의 문자열이다.

각 질의 단어에 대해, 알고리즘이 그 단어를 검색할 때 사용하는 단계 수를 한 줄에 하나씩 출력한다.

riseoj 작성

출처 COCI 2007/2008 Contest 5