1115: 最短的名字
Time Limit: 5 Sec Memory Limit:
64 MB
Submit: 141 Solved: 56
[Submit][Status][Web
Board]
Description
在一個奇怪的村子中，很多人的名字都很長，比如aaaaa, bbb and abababab。
名字這麼長，叫全名顯然起來很不方便。所以村民之間一般只叫名字的前綴。比如叫'aaaaa'的時候可以只叫'aaa'，因為沒有第二個人名字的前三個字母是'aaa'。不過你不能叫'a'，因為有兩個人的名字都以'a'開頭。村裡的人都很聰明，他們總是用最短的稱呼叫人。輸入保證村裡不會有一個人的名字是另外一個人名字的前綴（作為推論，任意兩個人的名字都不會相同）。
如果村裡的某個人要叫所有人的名字（包括他自己），他一共會說多少個字母？
Input
輸入第一行為數據組數T (T<=10)。每組數據第一行為一個整數n(1<=n<=1000)，即村裡的人數。以下n行每行為一個人的名字（僅有小寫字母組成）。輸入保證一個村裡所有人名字的長度之和不超過1,000,000。
Output
對於每組數據，輸出所有人名字的字母總數。
Sample Input
1
3
aaaaa
bbb
abababab
Sample Output
5
HINT
Source
湖南省第八屆大學生計算機程序設計競賽
這個題目上次看出是字典樹的題，思路也還是不清晰啊，昨天晚上寫也一直出現錯誤，今天把它的圖自己畫出來，思路就更加清晰了，再根據思路就容易把代碼寫出來啦，思路真的很重要！！！要增強自己的思維能力！
題目的思路是用字典樹儲存每個人的名字，如果名字前面的前綴相同，節點的計數就增加1，最後在把這些節點的標記的數目相加；圖畫的有點丑。
這個可以當做是自己的字典樹模板用啦，逐漸積累自己的模板；
#include
#include
#include
#include
using namespace std;
typedef struct node //節點的結構體
{
int count;//計數
struct node * next[26];//存儲的數組（按照題意來，可以變化的）
}node;
//char s[1010][10010];//這裡是看別人這樣寫，把一個大數組分成二維數組來寫（感覺內存浪費比較多）
char s[1000001];
node * newnode() //創建新節點
{
node *q;
q=(node*)malloc(sizeof(node));
q->count=1;
for(int i=0;i<26;i++)
q->next[i]=NULL;
return q;
}
void build(node *T,char *s) //建立字典樹
{
node *p;
p=T;
int len,k;
len=strlen(s);
for(int i=0;inext[k]==NULL)
{
p->next[k]=newnode();
// p->count=1; //先前把這個語句寫在這裡，答案就一直不對，後來寫到創建新節點的函數裡面就對了
p=p->next[k];
/*node *NewNode = (node*) malloc (sizeof (node)); //這裡是另一種寫法，在用的時候再臨時創節點
NewNode->count = 1;
for (int j = 0;j<26;j++) NewNode->next[j] = NULL;
p->next[k] = NewNode;
p = NewNode;*/
}
else
{
p=p->next[k];
p->count++;
}
}
}
int search(node *T) //查詢字典樹
{
node *q;
int sum=0;
q=T;
for(int i=0;i<26;i++)
{
if(T->next[i]!=NULL)
{
q=T->next[i];
sum+=q->count;
if(q->count>1)
{
sum+=search(q);
}
}
}
return sum;
}
void Release(node *T) //釋放內存
{
for(int i=0;i<26;i++)
if(T->next[i]!=NULL)
Release(T->next[i]);
//delete T;
free(T);
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
node *T;
T=(node *)malloc(sizeof(node));
T->count=0;
for(int i=0;i<26;i++)
T->next[i]=NULL;
scanf("%d\n",&n);
for(int i=0;i
