题目链接

/*

简单trie树的应用，注意在初始化的时候要把cnt也初始化，不然，WA！

下面的四分代码各有特点

*/

//数组型，名字查询。

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=1000000;

struct tire{

    int wd[27];

    int cnt;

    void init()

    {

        cnt=0;

        memset(wd,0,sizeof(wd));

    }

};

tire tree[maxn];

int tot=1,n,m;

void Insert(char* s,int root)

{

    for(int i=0;s[i];i++)

    {

        int k=s[i]-'a';

        if(!tree[root].wd[k])

        {

            tree[tot].init();

            tree[root].wd[k]=tot++;

        }

        root=tree[root].wd[k];

        tree[root].cnt++;

    }

}

int sum=0;

int query (int root)

{

    int sum=0;

    for(int i=0;i<=25;i++)

    {

        if(tree[root].wd[i])

        {

            int ro=tree[root].wd[i];

            sum+=tree[ro].cnt;

            if(tree[ro].cnt>1)

                sum+=query(ro);

        }

    }

    return sum;

}

char name[1000000+5];

int main ()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        int root=0;

        tot=1;

        tree[root].init();

        int n;scanf("%d",&n);

        for(int i=1;i<=n;i++)

        {

            scanf("%s",name);

            Insert(name, root);

        }

        printf("%d\n",query(root));

    }

    return 0;

}

//指针型，DFS查询

#include<cstdio>

#include<cstring>

#include<iostream>

const int maxn=1000000+5;

const int si=26;

int n;

char name[maxn];

struct node

{

    int n;

    node *chi[si];

    void init()

    {

        n=0;

        for(int i=0;i<si;i++)

            chi[i]=NULL;

    }

};

void Insert(char *s,node *root)

{

    for(int i=0;s[i];i++)

    {

        if(root->chi[s[i]-'a']==NULL)

        {

            node *t=(node *)malloc(sizeof(node));

            t->init();

            root->chi[s[i]-'a']=t;

        }

        root=root->chi[s[i]-'a'];

        root->n++;

    }

}

int query(node *root)

{

    int sum=0;

    for(int i=0;i<si;i++)

    {

        if(root->chi[i]!=NULL)

        {

            node *t=root->chi[i];

            sum+=t->n;

            if(t->n>=2)

                sum+=query(t);

        }

    }

    return sum;

}

void rease(node *root)

{

    for(int i=0;i<si;i++)

    {

        if(root->chi[i]!=NULL)

            rease(root->chi[i]);

    }

    delete root;

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        int n=0;

        scanf("%d",&n);

        node *root=(node *)malloc(sizeof(node));

        root->init();

        for(int i=0;i<n;i++)

        {

            scanf("%s",name);

            Insert(name, root);

        }

        printf("%d\n",query(root));

    }

}

//数组型，DFS查询

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=1000000;

struct tire{

    int wd[27];

    int cnt;

    void init()

    {

        cnt=0;

        memset(wd,0,sizeof(wd));

    }

};

tire tree[maxn];

int tot=1,n,m;

void Insert(char* s,int root)

{

    for(int i=0;s[i];i++)

    {

        int k=s[i]-'a';

        if(!tree[root].wd[k])

        {

            tree[tot].init();

            tree[root].wd[k]=tot++;

        }

        root=tree[root].wd[k];

        tree[root].cnt++;

    }

}

int sum=0;

int query (int root)

{

    int sum=0;

    for(int i=0;i<=25;i++)

    {

        if(tree[root].wd[i])

        {

            int ro=tree[root].wd[i];

            sum+=tree[ro].cnt;

            if(tree[ro].cnt>1)

                sum+=query(ro);

        }

    }

    return sum;

}

char name[1000000+5];

int main ()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        int root=0;

        tot=1;

        tree[root].init();

        int n;scanf("%d",&n);

        for(int i=1;i<=n;i++)

        {

            scanf("%s",name);

            Insert(name, root);

        }

        printf("%d\n",query(root));

    }

    return 0;

}

//数组型，名字查询，名字在string中保存，虽然可以节约空间，但是由于string只能用cin输入，所以时间慢。

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

using namespace std;

const int maxn=1000000;

struct tire

{

    int wd[27];

    int cnt;

    void init()

    {

        cnt=0;

        memset(wd,0,sizeof(wd));

    }

};

tire tree[maxn];

int tot=1,n,m;

void Insert(string s,int root)

{

    for(int i=0;s[i];i++)

    {

        int k=s[i]-'a';

        if(!tree[root].wd[k])

        {

            tree[tot].init();

            tree[root].wd[k]=tot++;

        }

        root=tree[root].wd[k];

        tree[root].cnt++;

    }

}

int query (string s,int root)

{

    for(int i=0;s[i];i++)

    {

        int k=s[i]-'a';

        root=tree[root].wd[k];

        if(tree[root].cnt==1)

            return i+1;

    }

    return tree[root].cnt+1;

}

string name[1000+5];

int main ()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        int root=0;

        tot=1;

        tree[root].init();

        int n;scanf("%d",&n);

        for(int i=1;i<=n;i++)

        {

            cin>>name[i];

            Insert( name[i], root);

        }

        int  ans=0;

        for(int i=1;i<=n;i++)

        {

            ans+=query(name[i], root);

        }

        printf("%d\n",ans);

    }

    return 0;

}