【CSU-1115】解题报告（字典树）

原始题目

1115: 最短的名字

  • Time Limit: 5 Sec
  • Memory Limit: 64 Mb
  • Submitted: 2057
  • Solved: 801

Description

在一个奇怪的村子中，很多人的名字都很长，比如 aaaaa, bbb and abababab。

名字这么长，叫全名显然起来很不方便。所以村民之间一般只叫名字的前缀。比如叫'aaaaa'的时候可以只叫'aaa'，因为没有第二个人名字的前三个字母是'aaa'。不过你不能叫'a'，因为有两个人的名字都以'a'开头。村里的人都很聪明，他们总是用最短的称呼叫人。输入保证村里不会有一个人的名字是另外一个人名字的前缀（作为推论，任意两个人的名字都不会相同）。

如果村里的某个人要叫所有人的名字（包括他自己），他一共会说多少个字母？

Input

输入第一行为数据组数\(T (T≤10)\)。每组数据第一行为一个整数 n\((1≤n≤1000)\) ，即村里的人数。以下\(n\)行每行为一个人的名字（仅有小写字母组成）。输入保证一个村里所有人名字的长度之和不超过 \(10^{6}\)。

Output

对于每组数据，输出所有人名字的字母总数。

Sample Input

1
3
aaaaa
bbb
abababab

Sample Output

5

Hint

Source

湖南省第八届大学生计算机程序设计竞赛

题目大意

如题

解题思路

建立字典树，每个结点的 value 值储存单词字母的出现次数。

  • 对于每个单词，统计第一个出现 value 值为 1 的位置（表示到这里后面没有相同单词前缀）
  • 求和，完成任务

解题代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <set>
#include <string>
#include <cstring>
#include <stack>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
using namespace std;
const int maxn=1e5+5;
const int maxl=26;

typedef long long ll;
typedef struct Trie
{
	int v;
	Trie* next[maxl];
}Trie;

Trie *root;
void iniTrie()
{
	root=(Trie*)malloc(sizeof(Trie));
	for(int i=0;i<maxl;i++)
		root->next[i]=NULL;
	root->v=-1;
}

bool creTrie(string a)
{
	int l=a.length();
	Trie *p=root,*q;
	for(int i=0;i<l;i++)
	{
		int id=a[i]-'a';
		//并非前缀不能有相同，而是不能在相同的分支上。
//		if(i==l-1){
//			if(p->next[id]!=NULL) return 0;
//		}
		if(p->next[id]==NULL){

			q=(Trie*) malloc(sizeof(Trie));
			q->v=1;
			for(int j=0;j<maxl;j++)
				q->next[j]=NULL;
			//
			//结点连接到树上
			p->next[id]=q;
			p=p->next[id];

		}
		else{
			p=p->next[id];
			p->v++;
		}
	}
	return 1;
}
int cntTrie(string ss)
{
	int l=ss.length();
	Trie *p=root,*q;
	for(int i=0;i<l;i++)
	{
		int id=ss[i]-'a';
		p=p->next[id];
		if(p->v==1) return i+1;

	}
}

void delTrie(Trie *p)
{
    int i;
    for(i=0;i<maxl;i++)
    {
        if(p->next[i] != NULL)
            delTrie(p->next[i]);
    }
    free(p);
//    printf("1");
	p==NULL;
	return ;
}


string s[maxn];
int t,ccount,n;
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		iniTrie();
		cin>>n;
		rep(i,0,n){
			cin>>s[i];
			creTrie(s[i]);
		}
		int aans=0;
		rep(i,0,n){
			aans+=cntTrie(s[i]);
		}
		cout<<aans<<endl;
		delTrie(root);
	}
}

收获与反思

灵活运用字典树的染色和统计功能