题解 CF898C 【Phone Numbers】

题目链接(洛谷)

题目链接(Codeforces)

类似的处理字符串后缀的题,第一反应就应该是字典树,对于处理字符串前后缀,没有什么数据结构能比字典树梗简单和快速了。

名字有多个,考虑以名字为映射建立多个字典树。

因为处理后缀,而字典树适用于前缀,所以对每个电话号码翻转,用倒序插入,将后缀变成前缀。

在插入字符串的过程中,路径上所经过的字符串,一定是这个字符串的前缀,每次插入,顺便删除路径上的前缀并判断是否有比当前字符串还要长的字符串,并且顺便存储正序字符串。

这样的方式,最后只保留相同后缀的所有字符串中长度最长的一个字符串。

之后对字典树进行遍历,将最后找到的字符串保存,并进行计数(推荐使用vector向量容器,方便插入且方便计数)。

最后按题目要求把字符串输出来即可。

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
#include<bits/stdc++.h>
using namespace std;

typedef struct Trie_node//数据结构
{
bool key;
struct Trie_node* next[10];
char str[20];
}TrieNode, *Trie;

int cnt;
Trie root[30];//根
map<string,int> name_num;//名字和根序号的映射
string namelist[30]; //记录所有的名字

int n;
char phone[20];
vector<string> phonenum[30];//存储名字对应的字符串

TrieNode* creat()//新建节点
{
Trie root=(TrieNode*)malloc(sizeof(TrieNode));
root->key=0;
memset(root->next,0,sizeof(root->next));
return root;
}

void insert(Trie root,char* word)
{
Trie rot=root;
char* p=word;
int id;
while(*p)
{
id=*p-'0';
if(rot->next[id]==NULL)
rot->next[id]=creat();
rot->key=0;
rot=rot->next[id];
p++;
}
if(rot->key)
return ;
for(int i=0;i<10;i++)
if(rot->next[i]!=NULL)
return ;
strcpy(rot->str,phone);//存储节点
rot->key=1;
}

void dfs(Trie pos,int name)
{
if(pos->key)
{
string tmp;
tmp.resize(20);
sprintf(&tmp[0],"%s",pos->str);
phonenum[name].push_back(tmp);//保存电话号码
}
for(int i=0;i<10;i++)
if(pos->next[i]!=NULL)
dfs(pos->next[i],name);
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int num;
string name;
name.resize(15);
scanf("%s%d",&name[0],&num);
if(name_num[name]==0)//建立映射关系
{
name_num[name]=++cnt;
root[name_num[name]]=creat();
namelist[name_num[name]]=name;
}
for(int j=1;j<=num;j++)
{
char tmp[20];
scanf("%s",phone);
int len=strlen(phone);
for(int k=0;k<=len;k++)
tmp[k]=phone[len-k-1];//翻转字符串
insert(root[name_num[name]],tmp);
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%s ",namelist[i].c_str());
dfs(root[i],i);
printf("%d ",phonenum[i].size());
for(int j=0;j<phonenum[i].size();j++)
printf("%s ",phonenum[i][j].c_str());
puts("");
}
}