UVA 12506 Shortest Names (E)

Shortest Names

In a strange village, people have very long names. For example: aaaaa, bbb and abababab.

You see, it's very inconvenient to call a person, so people invented a good way: just call a prefix of the names. For example, if you want to call `aaaaa', you can call `aaa', because no other names start with `aaa'. However, you can't call `a', because two people's names start with `a'. The people in the village are smart enough to always call the shortest possible prefix. It is guaranteed that no name is a prefix of another name (as a result, no two names can be equal).

If someone in the village wants to call every person (including himself/herself) in the village exactly once, how many characters will he/she use?

Input

The first line contains T (T10), the number of test cases. Each test case begins with a line of one integer n ( 1n1000), the number of people in the village. Each of the following n lines contains a string consisting of lowercase letters, representing the name of a person. The sum of lengths of all the names in a test case does not exceed 1,000,000.

Output

For each test case, print the total number of characters needed.

Sample Input

1
3
aaaaa
bbb
abababab

Sample Output

5

思路：先排个序，那么前缀要不一样，要最短，肯定是跟前一个比较或者后一个，取大的那个即可。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <string>
 5 #include <iomanip>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <vector>
 9 #include <map>
10 using namespace std;
11 #define maxn 1010
12 string s[maxn];
13 int T, n, len1, len2, cnt;
14 int last[maxn], next[maxn];
15 int main(){
16     scanf("%d", &T);
17     while(T--){
18         scanf("%d", &n);
19         for(int i = 1; i <= n; i++) cin>>s[i];
20         sort(s+1,s+1+n);
21         cnt = 0;
22         for(int i = 1; i <= n; i++){
23             if(i == 1) last[i] = 0; //上一个 
24             else last[i] = next[i-1];
25             
26             if(i == n) next[i] = 0;
27             else{
28                 len1 = s[i].size(); len2 = s[i+1].size();
29                 int j;
30                 for( j = 0; j < len1 && j < len2; j++){
31                     if(s[i][j] != s[i+1][j]){
32                         break;
33                     }
34                 }
35                 next[i] = j+1; //next表示i和i+1，last表示i和i-1即 next[i-1]; 
36             }
37             cnt += next[i]>last[i]?next[i]:last[i]; 
38             
39         }
40         printf("%d
", cnt);
41     }
42     
43     return 0;
44 }