[문제요약] The longest common prefix of two words is the longest word that both words start with. 두 단어의 가장 긴 공통 접두어는 처음부터 일치하는 가장긴 단어이다. For example, the longest common prefix of the words "identity" and "idealistic" is the word "ide". A database contains N words. 예를 들어 , identity" 와 "idealistic 는 가장 긴 접두어는 ide 이다.
The algorithm to search for a query word W in the database is primitive. 여러 단어 중 가장 긴 접두어를 찾는 알고리즘은 ... It compares the word W one by one with each word in the database. 데이터베이스에서 단어 W 를 하나씩 비교해서 Two words are compared letter by letter until a letter in which they differ is found or until the end of one of the words is reached (it is then established either that the words are equal or that one is longer than the other). When the algorithm finds the word W in the database, it terminates.
Analysing the algorithm shows that the number of steps needed to find a word W is equal to the number of words W is compared to, plus the sum of the lengths of the longest common prefixes of W and each of the words it was compared to.
Write a program that calculates the number of steps the algorithm uses to find each of the Q query words. In the second example, the number of steps to search for the word "krampus" is 8 because the algorithm only needs to compare its first letter to each word in the database. 입출력 예의 두번째 예를 들어 단어 "krampus" 를 찾는 스텝의 수는 8 이다. 왜냐하면 이 단어의 첫자를 비교할 때 필요로 한다..
When searching for the word "malnar", we need three steps for each of the first three words, and four steps for each of the remaining five words, for a total of 29 steps. "malnar"를 검색할 때는 처음 세 단어 각각에 3 스텝이 필요하다.
To find the word "majmun" we use a total of 14 steps. For the first word in the database, we have six successful comparisons and one step in which we determine that the word "majmunica" is longer than the query word. For the second word, we also have six successful comparisons and a final step in which it is established that the words are equal. After finding the word, the algorithm terminates with great joy.
The algorithm to search for a query word W in the database is primitive. It compares the word W one by one with each word in the database. Two words are compared letter by letter until a letter in which they differ is found or until the end of one of the words is reached (it is then established either that the words are equal or that one is longer than the other). When the algorithm finds the word W in the database, it terminates.
Analysing the algorithm shows that the number of steps needed to find a word W is equal to the number of words W is compared to, plus the sum of the lengths of the longest common prefixes of W and each of the words it was compared to.
Write a program that calculates the number of steps the algorithm uses to find each of the Q query words.
input 5 hobotnica robot hobi hobit robi 4 robi hobi hobit rakija output 12 10 16 7 input 8 majmunica majmun majka malina malinska malo maleni malesnica 3 krampus malnar majmun output 8 29 14
When searching for the word "malnar", we need three steps for each of the first three words, and four steps for each of the remaining five words, for a total of 29 steps.
To find the word "majmun" we use a total of 14 steps. For the first word in the database, we have six successful comparisons and one step in which we determine that the word "majmunica" is longer than the query word. For the second word, we also have six successful comparisons and a final step in which it is established that the words are equal. After finding the word, the algorithm terminates with great joy.
출처: