UVA - 11732 "strcmp()" Anyone? （trie）

题意

给定n个字符串，问用strcmp函数比较这些字符串共用多少次比较。

strcmp函数的实现

int strcmp(char *s, char *t)

{

    int i;

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

        if (s[i]=='\0')

            return ;

    return s[i] - t[i];

}

分析

建trie树，把‘\0’也加进去，记录以每个节点为子树包含的单词节点。

然后dfs计数，遇到单词节点，说明可能存在相同的字符串，于是此时ans+=tot[u]*(tot[u]-1)*dep；

否则就是（2*dep+1）*sum，sum为所有选法。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

//#define eps 0.0000000001

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1)

//const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn =  *  + ;

const int maxm = 4e5 +;

const int mod = ;

const int sigma_size = ;

struct Trie{

    int head[maxn];// head[i]为第i个结点的左儿子编号

    int nxt[maxn];// next[i]为第i个结点的右兄弟编号

    char ch[maxn];// ch[i]为第i个结点上的字符

    int tot[maxn];// tot[i]为第i个结点为根的子树包含的叶结点总数

    int sz;

    ll ans;// 答案

    void init(){

        sz=;

        tot[]=head[]=nxt[]=;

    }

    // 插入字符串s（包括最后的'\0'），沿途更新tot

    void insert(char* s){

        int u=,v,n=strlen(s);

        tot[]++;

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

            // 找字符a[i]

            bool f=false;

            for(v=head[u];v;v=nxt[v]){

                if(ch[v]==s[i]){// 找到了

                    f=true;

                    break;

                }

            }

            if(!f){

                v=sz++;// 新建结点

                tot[v]=;

                ch[v]=s[i];

                nxt[v]=head[u];

                head[u]=v;// 插入到链表的首部

                head[v]=;

            }

            u = v;

            tot[u]++;

        }

    }

      // 统计LCP=u的所有单词两两的比较次数之和

    void dfs(int dep,int u){

        // 叶结点

        if(head[u]==) ans+=tot[u]*(tot[u]-)*dep;

        else{

            int sum=;

            for(int v=head[u];v;v=nxt[v]){

                sum+=tot[v]*(tot[u]-tot[v]);

                // 子树v中选一个串，其他子树中再选一个

            }

            // 除以2是每种选法统计了两次

            ans+=sum/*(*dep+);

            for(int v=head[u];v;v=nxt[v])

                dfs(dep+,v);

        }

    }

    ll cal(){

        ans=;

        dfs(,);

        return ans;

    }

};

Trie trie;

char tmp[];

int main() {

#ifdef LOCAL

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

//    freopen("input.txt", "w", stdout);

#endif

    int cas=;

    int T;

    while(~scanf("%d",&T)&&T){

        trie.init();

        for(int i=;i<T;i++){

            scanf("%s",tmp);

            trie.insert(tmp);

        }

        printf("Case %d: %lld\n",cas++,trie.cal());

    }

    return ;

}