D |
Anti-Rhyme
Pairs Input: Standard Input Output: Standard Output |
|
Often two words that rhyme also
end in the same sequence of characters. We use this property to define the
concept of an anti-rhyme. An anti-rhyme is a pair of words that have a similar beginning.
The degree of anti-rhyme of a pair of words is further defined to be the length
of the longest string S such that
both strings start with S. Thus,
“arboreal” and “arcturus” are an anti-rhyme pair of degree 2, while
“chalkboard” and “overboard” are
an anti-rhyme pair of degree 0.
You are given a list of words. Your task is, given a list of queries in the form (i, j), print the degree of anti-rhyme for the pair of strings formed by the i-th and the j-th words from the list.
Input consists of a number of test cases. The first line of input contains the number of test cases T (T ≤ 35). Immediately following this line are T cases.
Each case starts with the number of strings N (1 ≤ N ≤ 105) on a line by itself. The following N lines each contain a single non-empty string made up entirely of lower case English characters ('a' to 'z'), whose length L is guaranteed to be less than or equal to 10,000. In every case it is guaranteed that N*L ≤ 106.
The line following the last string contains a single integer Q (1 ≤ Q ≤ 106), the number of queries. Each of the Q lines following contain a query made up of two integers i and j separated by whitespace (1 ≤ i, j ≤ N).
The output
consists of T cases, each starting with
a single line with “Case X:”, where X indicates the X-th case. There should be exactly Q lines after that for each case. Each of those Q lines should contain an integer that
is the answer to the corresponding query in the input.
2 5 daffodilpacm daffodiliupc distancevector distancefinder distinctsubsequence 4 1 2 1 5 3 4 4 5 2 acm icpc 2 1 2 2 2 |
Case 1: 8 1 8 4 Case 2: 0 4 |
Warning: I/O files is huge, make sure your I/O is fast.