UVA 11732 strcmp() Anyone （Trie+链表）

先两两比较，比较次数是两者相同的最长前缀长度*2+1，比较特殊的情况是两者完全相同时候比较次数是单词长度*2+2，

两个单词'末尾\0'和'\0'比较一次，s尾部'\0'和循环内'\0'比较一次。

因此，对于一个单词，只要知道和它某个相同的最长前缀的单词数就可以计算出方案数了。

用tire，记录一颗子树上的结点数cnt[u]（用于计算当前前缀是最长前缀的单词数）和在某个结点终止的单词数val[u]（处理特殊情况）。

因为字符集比较大，可能会有较大的空间浪费，所以用一个链式的结构保存子节点。（查找子节点的时候效率会低一些）。

如果插完了以后再统计的话一个前缀会被算2次，要除以2。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxnds = *+;

char ch[maxnds];//用来保存结点的字符值

int cnt[maxnds];

int son[maxnds],bro[maxnds]; //son是链表头，bro[u]表示u的下一个兄弟结点

int val[maxnds];

int nds;//nds是下一个可以分配的结点

void init()

{

    nds = ; cnt[] = son[] = val[] = ;

}

ll add(char *s)

{

    ll ret = ;

    int u = ,v,i;

    for(i = ; s[i]; i++){

        for(v = son[u]; v; v = bro[v]){

            if(ch[v] == s[i]) break;

        }

        if(!v){

            //初始化新结点

            bro[nds] = son[u];

            ch[nds] = s[i];

            val[nds] = cnt[nds] = son[nds] = ;

            //把新结点插到链表头，并分配下一个结点

            v = son[u] = nds++;

        }

        ret += (cnt[u]-cnt[v])*(i<<|);

        cnt[u]++;

        u = v;

    }

    if(val[u]) ret += val[u]*((i+)<<);

    ret += (cnt[u]-val[u])*(i<<|);

    cnt[u]++; val[u]++;

    return ret;

}

char str[];

int main()

{

    //freopen("in.txt","r",stdin);

    int N,kas = ;

    while(scanf("%d\n",&N),N){

        ll ans = ;

        init();

        while(N--){

            gets(str);

            ans += add(str);

        }

        printf("Case %d: %lld\n",++kas,ans);

    }

    return ;

}

巴特西

UVA 11732 strcmp() Anyone （Trie+链表）

最新文章

热门文章