最短的名字（湖南省第八届大学生计算机程序设计竞赛）
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=30746#problem/E
最短的名字Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%lld & %lluSubmit Status Practice CSU 1115

Description

Input

Output

Sample Input

1 3 aaaaa bbb abababab

Sample Output

5

用字典树。AC代码：

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;char s[1001][10001];struct node{    int v;    char now;    node *next[26];};node root;void biuld(char *str)   //创建字典树{    int i,len;    len = strlen(str);    node *p = &root,*q;    for(i = 0; i < len; i++)    {        int id = str[i]-'a';        if(p->next[id]==NULL)        {            q=(node *)malloc(sizeof(root));            q->v = 1;            for(int j = 0; j < 26; j++)            {                q->next[j] = NULL;            }            p->next[id] = q;            p=p->next[id];        }        else        {            p->next[id]->v++;            p=p->next[id];        }    }}/*void Dfs(int k,){}*/int findTrie(char *str){    int i;    int len=strlen(str);    node *p=&root;    for(i=0;i<len;i++)    {        int id=str[i]-'a';        p=p->next[id];        if(p->v<=1)        {            return i+1;        }    }    return i;}int main(){    int sum;    int t,n,i;    scanf("%d",&t);    while(t--)    {        for(i = 0; i < 26; i++)  //重置根节点        {            root.next[i] = NULL;        }        sum = 0;        scanf("%d",&n);        for(i = 0; i < n; i++)        {            scanf("%s",&s[i]);            biuld(s[i]);        }        for(i = 0; i < n; i++)        {            sum+=findTrie(s[i]);        }        printf("%d\n",sum);    }    return 0;}