Time Limit: 1000 ms Memory Limit: 64 MB
Total Submission: 25 Submission Accepted: 11
Judge By Case
Description
西瓜在写编译原理作业中的文法分析器的时候，通常需要检测一个单词是否在给定的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
在满足上述条件下，该单词查找树的节点数最少。
例：图一的单词列表对应图二的单词查找树
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）
Input
输入一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符，单词个数不超过5000。
Output
输出仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。
Sample Input
OriginalTransformed
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
A[EOL]
AN[EOL]
ASP[EOL]
AS[EOL]
ASC[EOL]
ASCII[EOL]
BAS[EOL]
BASIC[EOF]
Sample Output
OriginalTransformed
13
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
//#define DEBUG
using namespace std;
#define MAX 26
const int maxn = 70;
typedef struct Trie {
Trie *next[MAX];
int v;
};
Trie *root = (Trie*)malloc(sizeof(Trie));
int ans;
void createTrie(char *str);
int findTrie(char *str);
int findTrie(char *str);
void findNode(Trie *t);
int main() {
#ifdef DEBUG
freopen("Text.txt", "r", stdin);
#endif // DEBUG
char c[maxn];
for (int i = 0; i < MAX; i++)
root->next[i] = NULL;
root->v = 0;
memset(root->next, NULL, sizeof(root->next));
while (cin >> c) {
//cout << c << endl;
createTrie(c);
}
ans = 0;
findNode(root);
cout << ans << endl;
return 0;
}
void createTrie(char *str) {
int len = strlen(str);
Trie *p = root, *q;
cout << "Error" << endl;
for (int i = 0; i < len; i++) {
int id = str[i] - 'A';
if (p->next[id] == NULL) {
q = (Trie*)malloc(sizeof(Trie));
q->v = 1;
for (int j = 0; j < MAX; j++)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else{
p->next[id]->v++;
p = p->next[id];
}
}
p->v = -1;
}
int findTrie(char *str) {//本题不需要
Trie* p = root;
int len = strlen(str);
for (int i = 0; i < len; i++) {
int id = str[i] - 'A';
p = p->next[id];
if (p == NULL)
return 0;
if (p->v == -1)
return -1;
}
return -1;
}
void dealTrie(Trie* t) {//本题不需要
if (t == NULL)
return;
for (int i = 0; i < MAX; i++)
if(t->next[i]!=NULL)
dealTrie(t->next[i]);
free(t);
}
void findNode(Trie *t) {
if (t == NULL)
return;
for (int i = 0; i < MAX; i++) {
if (t->next[i] != NULL)
findNode(t->next[i]);
}
ans++;
}
