UVA 12338 Anti-Rhyme Pairs (最长公共前缀)

Anti-Rhyme Pairs

Time Limit: 5000ms

Memory Limit: 131072KB

Often two words that rhyme alsoend in the same sequence of characters. We use this property to define theconcept 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 lengthof the longest string S such thatboth strings start with S. Thus,arboreal and arcturus are an anti-rhyme pair of degree 2, whilechalkboard and overboard arean 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 stringsformed by the i-th and the j-th words from the list.

Input

Input consists of a number oftest cases. The first line of input contains the number of test cases T (T ≤ 35).Immediately following this line are Tcases.

Each case starts with the numberof strings N (1 ≤ N ≤10⁵) on a line by itself. The following N lines each contain a single non-emptystring made up entirely of lower case English characters ('a' to 'z'), whoselength L is guaranteed to be lessthan or equal to 10,000. In everycase it is guaranteed that N*L ≤10⁶.

The line following the last stringcontains a single integer Q (1 ≤Q ≤ 10⁶), the number of queries. Each of theQ lines following contain a querymade up of two integers i and j separated by whitespace (1 ≤ i, j ≤N).

Output

The outputconsists of T cases, each starting witha 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 thatis the answer to the corresponding query in the input.

SampleInput Output for Sample Input

daffodilpacm

daffodiliupc

distancevector

distancefinder

distinctsubsequence

1 2

1 5

3 4

4 5

acm

icpc

1 2

2 2

Case 1:

Case 2:

Warning:I/O files is huge, make sure your I/O is fast.

题目链接：https://acm.bnu.edu.cn/v3/contest_show.php?cid=7985#problem/D

题目大意：给n个字符串，m个查询，求第x个和第y个的最长公共前缀长度

题目分析：对字符串按前缀hash，二分长度判断即可

 1 //2018年2月28日09:21:49
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8 
 9 const int maxn = 100100;
10 const int seed = 131;
11 const int mod = 1e9+7;
12 
13 typedef long long ll;
14 typedef unsigned long long ull;
15 int T, n, m;
16 char s[maxn];
17 vector<ull> v[maxn];
18 
19 int hash(char *s, int id){
20     int Hash = 0;
21     for(int i=0; s[i]; i++){
22         Hash = (Hash*seed + s[i]-'0') % mod;
23         v[id].push_back(Hash); 
24     }
25     return Hash;
26 }
27 
28 int main(){
29     scanf("%d", &T);
30     while(T--){
31         scanf("%d", &n);
32         for(int i=1;i<=n;i++){
33             scanf("%s", s);
34             v[i].clear();
35             hash(s, i);
36         }
37         scanf("%d", &m);
38         while(m--){
39             int a, b;
40             scanf("%d%d", &a, &b);
41             int l=0, r=min(v[a].size(), v[b].size())-1, ans=0;
42             while(l <= r){
43                 int mid = l+r >> 1;
44                 if(v[a][mid] == v[b][mid]) ans=mid, l=mid+1; 
45                 else r = mid-1;
46             }
47             if(v[a][ans] != v[b][ans])
48                 printf("%d
", ans);
49             else printf("%d
", ans+1);
50         }
51     }
52 
53     return 0;
54 }