단어 검색
면접 대비시간 제한1초메모리 제한128 MB
데이터베이스 단어들과 쿼리 단어를 순서대로 문자 단위로 비교하며 단어 끝 여부까지 확인할 때 필요한 총 비교 횟수를 구합니다.
문제
단어가 N개 저장된 데이터베이스가 있다.
검색 알고리즘은 검색어 W를 데이터베이스의 단어와 입력된 순서대로 하나씩 비교한다. 두 단어를 비교할 때는 맨 앞 글자부터 차례대로 비교하며, 서로 다른 글자가 나오거나 한쪽 단어의 끝을 확인할 때까지 진행한다. 검색어와 같은 단어를 찾으면 그 즉시 검색을 멈춘다.
단어의 길이는 비교하기 전에는 알 수 없다고 가정한다. 따라서 마지막 글자까지 모두 같더라도, 그 다음 위치를 한 번 더 비교해야 단어가 끝났는지 알 수 있다. 예를 들어 abc와 abcd를 비교하면 네 번째 위치에서 한쪽 단어가 끝났다는 것을 확인하고 두 단어가 다르다고 판단한다. abc와 abc를 비교할 때도 네 번째 위치에서 두 단어가 모두 끝났음을 확인해야 같은 단어라고 판단한다.
검색어가 데이터베이스에 없으면 모든 단어와 비교한 뒤 검색이 끝난다. 단어 목록과 검색어들이 주어질 때, 각 검색어를 처리하는 데 필요한 문자 비교 횟수를 구하라.
입력
첫째 줄에 데이터베이스에 있는 단어의 개수 N이 주어진다. (1 <= N <= 30000)
다음 N개의 줄에는 데이터베이스에 있는 단어가 하나씩 주어진다. 검색할 때는 이 입력 순서를 그대로 사용해야 하며, 데이터베이스의 모든 단어는 서로 다르다.
다음 줄에 검색어의 개수 Q가 주어진다. (1 <= Q <= 30000)
다음 Q개의 줄에는 검색어가 하나씩 주어진다.
모든 단어와 검색어는 알파벳 소문자로만 이루어져 있으며, 길이는 30보다 작다.
출력
각 검색어마다, 그 검색을 마칠 때까지 필요한 문자 비교 횟수를 한 줄에 하나씩 출력한다.