uva 11732 – strcmp() Anyone? 不错的Trie题

题解：http://blog.csdn.net/u013480600/article/details/23122503

我的代码一直TLE,,,看了人家的之后，认为1、链式前向星比較好，2、*depth而不是每过一个节点就计算，这一点非常好

我是基本copy别人的代码，自己加了凝视，留个记号，随后重写，

这道题相同作为链式前向星的Trie的模板

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
#define ll long long
const int MAXN=4002*1002+100;

struct Trie
{
    int head[MAXN];//其值为在边集的下标
    int next[MAXN];//next[j]第j条边的下一条边在边集的下标
    int tot[MAXN];
    char str[MAXN];//相当于边集了 边存储字符
    int sz;//head下标的上界,也相当于节点
    ll ans;
    void clear()
    {
        ans=0;
        sz=1;
        head[0]=next[0]=tot[0]=0;

    }
    void insert(char *s)
    {
        int n=strlen(s),u=0;
        tot[u]++;
        for(int i=0;i<=n;i++)//空字符也插入
        {
            bool found=false;
            for(int j=head[u];j;j=next[j])
                if(str[j] == s[i])
                {
                    u=j;
                    found=true;
                    break;
                }
            if(!found)//节点不存在
                {
                    next[sz]=head[u];
                    head[u]=sz;

                    head[sz]=0;//
                    tot[sz]=0;//新的节点还没有连边
                    str[sz]=s[i];//初始化边信息，边存储字符
                    u=sz++;//u存储新的子结点
                }
                tot[u]++;
        }
    }
    void dfs(int dep, int u)
    {
        if(!head[u])//到了叶子节点
        {
            ans+=tot[u]*(tot[u]-1)*dep;
        }
        else
        {
            int sum=0;
            for(int v=head[u];v;v=next[v])  //**
                sum+=tot[v]*(tot[u]-tot[v]);//**
            ans+= sum/2*(dep*2+1);//这里我自己做的时候没有想到，，，，事实上分叉后跟分叉前都能够用上面标注**的方法计算
            for(int v=head[u];v;v=next[v])
                dfs(dep+1,v);
        }
    }
    ll cal()
    {
        ans=0;
        dfs(0,0);
        return ans;
    }
};
Trie trie;
char word[1000+100];
int main()
{

    int icase=0,n;
    while(scanf("%d",&n) && n)
    {
        trie.clear();
        for(int i=0;i<n;i++)
        {
            scanf("%s",word);
            trie.insert(word);
        }
        printf("Case %d: %lld\n",++icase,trie.cal());
    }
    return 0;
}

我的tle的代码  随后改动

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define ll long long

const int N = 4011*1000+10;
const int tk = 75;
const int tb = '0'; // tk叉; 起始字母为tb;
int top, tree[N][tk + 2];  // N: 最大结点个数 top: 第一层有多少节点
char str[1010];
void init(){
    top = 1;
    memset(tree[0], 0, sizeof(tree[0]));
}

void Insert(char*s, int Rank = 1){
    int rt, nxt;
    for(rt = 0; *s; rt = nxt, ++s) {
        nxt = tree[rt][*s - tb];

        if(0 == nxt) {//没被使用时插入
            tree[rt][*s - tb] = nxt = top;
            memset(tree[top], 0, sizeof(tree[top]));
            top++;
        }
        tree[nxt][tk]++;//其值表示有多少单词经过
    }
    tree[rt][tk+1] = Rank;//1表示存在0表示不存在，也能够赋予其其它含义
}

ll solve(int rt,int last)
{
    if(tree[rt][tk] <= 1)return 0;
    //到结尾仅仅须要比較一次，假设仅仅有一个，也仅仅须要比較一次
    ll ans=0;
    for(int i=0;i<tk;i++)
        if(tree[rt][i])
        {
            ans=ans+tree[tree[rt][i]][tk]*(last-tree[tree[rt][i]][tk]);//计算子树森林
        }

    ans/=2;
    for(int i=0;i<tk;i++)
    {
        if(tree[rt][i])
        {
            ans+=solve(tree[rt][i],tree[tree[rt][i]][tk]);
        }

    }
    //return ans+2*C[tree[rt][tk]][2];
    return ans+tree[rt][tk]*(tree[rt][tk]-1);
}
int main()
{
    freopen("uva11732.txt","r",stdin);
    int icase=0,n,len;
    //calC();
    while(scanf("%d",&n)==1 && n)
    {
        init();
        tree[0][tk]=n;
        for(int i=0;i<n;i++)
        {
            scanf("%s",str);
            Insert(str);
        }

        printf("Case %d: %lld\n",++icase,solve(0,n)-n*(n-1));
    }
    return 0;
}