UVA 11732 strcmp() Anyone? Trie的左儿子右兄弟表示法

        思考了一会儿，发现这题目要一层层的考虑。

        即，在插入一个字符串str到Trie的时候，同时更新答案

        两个字符串，在对比到第i个位置不同时，通过的比较次数是(i<<1)+1，注意，此处i是从0开始的。

        假若到最后都相同的话，比较的次数是(length+1)<<1，即length*2+2，要考虑末尾的/0

        抱着这样的想法，我发现普通的Trie并不好维护这个玩意，看了题解才明白。

        没想到在这里遇见了左儿子右兄弟表示法，也是，这个表示法是比较符合这个场景的

        边插入边计算答案，每到一层就+上那些当前位和自己不同的字符串的比较次数，到最后+上和自己相同的比较次数

        用val数组来维护当前通过该点的字符串个数

        总之感觉用法很好，在Trie中插入节点的时候有点数组模拟邻接表的感觉了

#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;int n,kcase=1,sz,bro[4000010],son[4000010],val[4000010];char str[1005],ch[4000010];void init(),ins(char* str);ll ans;int main(){    ios_base::sync_with_stdio(false);    while(cin>>n&&n){        init();        ans=0;        for(int i=0;i<n;++i){            cin>>str;            ins(str);        }        cout<<"Case "<<kcase++<<": "<<ans<<endl;    }    return 0;}void init(){    sz=1;    ch[0]=bro[0]=son[0]=val[0]=0;}void ins(char* str){    int len=strlen(str),u=0,p;    for(int i=0;i<=len;++i){        for(p=son[u];p;p=bro[p])        if(ch[p]==str[i])            break;        if(!p){            p=sz++;            ch[p]=str[i];            bro[p]=son[u];            son[p]=val[p]=0;            son[u]=p;        }        ans+=(val[u]-val[p])*((i<<1)+1);        if(len==i){            ans+=val[p]*((i+1)<<1);            ++val[p];        }        val[u]++;        u=p;    }}