Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 简单的字典树！计算经过每个节点测次数即可

Posted by 1214011013 at 2014-09-28 22:25:07 on Problem 2001
```#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
struct Trie
{
int cnt;//经过当前节点的
Trie *next[26];
Trie()
{
for(int i = 0; i < 26; i++)
next[i] = NULL;
cnt = 1;
}
};
Trie * root = NULL;
void Insert_Trie(char msg[])
{
int i = 0;
Trie * cur = root;
int k;
while(msg[i] )
{
k = msg[i] - 'a';
if(cur->next[k] == NULL)
cur->next[k] = new Trie();
else
{
cur->next[k]->cnt++;
}
cur = cur->next[k];
i++;
}
}
int search_Trie(char msg[])
{
int i = 0;
int k;
Trie *cur = root;
while(msg[i])
{
k = msg[i]  - 'a';
cur = cur->next[k];
if(cur->cnt <=1)
{
return i;
}
i++;
}
return -1;
}
char input[1002][25];
void Delete(Trie * root)
{
for(int i = 0; i < 26; i++)
{
if(root->next[i] != NULL)
Delete(root->next[i]);
}
delete root;
}
int main()
{
int nCount = 0;
root = new Trie();
while(gets(input[nCount]))
{
Insert_Trie(input[nCount]);
nCount++;
}
for(int i = 0; i < nCount; i++)
{
int cnt = search_Trie(input[i]);

if(cnt == -1)
{
printf("%s %s\n",input[i],input[i]);
}
else
{
char  prefix[22];
memset( prefix,0,sizeof( prefix));
printf("%s ",input[i]);
input[i][cnt + 1] = '\0';
strcat(prefix,input[i]);
printf("%s\n", prefix);
}
}
Delete(root);
return 0;
}
```

Followed by: