Problem definition can be found here.
This is a basic problem which can be solved directly by a Tri-tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <numeric>
#include <fstream>
#include <iostream>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <sstream>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i, n) for (int i(0); i < n; ++i)
#define REP1(i, n) for (int i(1); i < n; ++i)
#define FOR(i, a, b) for (int i(a); i <= b; ++i)
struct node {
node() {
childs = new node*[26];
REP(i, 26) childs[i] = NULL;
}
node** childs;
};
int tc;
int n;
string word;
int findWordAndBuildTree(node* root, string word) {
node* p = root;
int i = 0;
int res = 0;
bool found = false;
REP(i, word.length()) {
if (p->childs[word[i]-'a'] == NULL) {
if (!found) {
res = i + 1;
found = true;
}
p->childs[word[i]-'a'] = new node();
}
p = p->childs[word[i]-'a'];
}
return res;
}
int main(int argc, char* argv[]) {
cin >> tc;
REP(i, tc) {
cin >> n;
node* root = new node();
int res = 0;
REP(j, n) {
cin >> word;
res += findWordAndBuildTree(root, word);
}
cout << res << endl;
}
return 0;
}
|