給定若干字符串,輸出兩兩strcmp比較的時候每一次比較了多少次

UVA 11732
題目鏈接https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2832

說實(shí)話...這個想起來就頭疼

我們知道strcmp實(shí)際上是從頭比較到尾,也就是說實(shí)際上比較一次on也就可以了..但是這個輸入會有23兆

然后我們就可以思考,實(shí)際上strcmp的比較就是a[i]和b[i]相比,必然是對應(yīng)位置上面的比較.回想一下trie的構(gòu)建過程,實(shí)際上對于一棵字典樹,當(dāng)且僅當(dāng)有一個位置不同的時候我們才會將其進(jìn)行一個分叉,總共的比較次數(shù)實(shí)際上也就是訪問路上走過的路

所以就想到了對于所有的字符串構(gòu)建這樣的一棵字典樹,然后進(jìn)行一次dfs,遞歸到葉子節(jié)點(diǎn)之后,再返回父親節(jié)點(diǎn),將情況返回回去.

因?yàn)槲覀円呀?jīng)選定過一邊之后我們?nèi)砸@得另一邊的關(guān)系,這個獲取是盲目的,所以在獲取之后我們又要將結(jié)果除2

差不多了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>


using namespace std;
const int maxnode = 4e6 + 7;
const int sigma_size = 26;


struct Trie{
    int head[maxnode];//head[i]即i節(jié)點(diǎn)的左兒子是什么
    int next[maxnode];//next[i]保存了它的右邊的兄弟.
    char ch[maxnode];
    int tot[maxnode];tot[i]表示i節(jié)點(diǎn)的大小
    int sz;
    long long ans;
    void clear() {
        sz = 1;
        tot[0] = head[0] = next[0] = 0;
    }

    void insert(const char *s){
        int u = 0, v, n = strlen(s);
        tot[0] ++;
        for (int i = 0;i <= n;i ++){
            bool found = false;
            for (v = head[u]; v; v = next[v]){
                if (ch[v] == s[i]){
                    found = true;
                    break;
                }
            }
            if (!found){
                v = sz ++;
                tot[v] = 0;
                ch[v] = s[i];
                next[v] = head[u];
                head[u] = v;
                head[v] = 0;
            }
            u = v;
            tot[u] ++;
        }
    }

    void dfs(int depth, int u){
        if (head[u] == 0){
            ans += tot[u] * (tot[u] - 1) * depth;//遞歸到葉子,訪問父親是否有分叉,有分叉就納入答案
        }
        else{
            int sum = 0;
            for (int v = head[u]; v; v = next[v]){
                sum += tot[v] *(tot[u] - tot[v]);//作為父親節(jié)點(diǎn),選取一邊的答案,那么實(shí)際上另一邊的答案可以直接相乘
            }
            ans += sum / 2 * (2 * depth + 1);//但是由于這樣的選擇是盲目的,所以我們需要將其除2
            for (int v = head[u]; v ; v = next[v]){
                dfs(depth + 1, v);
            }
        }
    }

    long long count(){
        ans = 0;
        dfs(0, 0);
        return ans;
    }
};

const int maxl = 1010;

int n;
char word[maxl];
Trie trie;


int main(){
    int kase = 1;
    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", kase ++, trie.count());
    }
    return 0;
}