UVA 11732 —— 左兒子右兄弟表示法&&Tire

11732 - strcmp() Anyone?

Time limit: 2.000 seconds

J	“strcmp()” Anyone? Input: Standard Input Output: Standard Output

strcmp() is a library function in C/C++ which compares two strings. It takes two strings as input parameter and decides which one is lexicographically larger or smaller: If the first string is greater then it returns a positive value, if the second string is greater it returns a negative value and if two strings are equal it returns a zero. The code that is used to compare two strings in C/C++ library is shown below:

int strcmp(char *s, char *t) {     int i;     for (i=0; s[i]==t[i]; i++)         if (s[i]=='\0')             return 0;     return s[i] - t[i]; }

Figure: The standard strcmp() code provided for this problem.

The number of comparisons required to compare two strings in strcmp() function is never returned by the function. But for this problem you will have to do just that at a larger scale. strcmp() function continues to compare characters in the same position of the two strings until two different characters are found or both strings come to an end. Of course it assumes that last character of a string is a null (‘\0’) character. For example the table below shows what happens when “than” and “that”; “therE” and “the” are compared using strcmp() function. To understand how 7 comparisons are needed in both cases please consult the code block given above.

t	h	a	N	\0	t	h	e	r	E	\0
=	=	=	≠	=	=	=	≠
t	h	a	T	\0	t	h	e	\0
Returns negative value 7 Comparisons	Returns positive value 7 Comparisons

Input

The input file contains maximum 10 sets of inputs. The description of each set is given below:

Each set starts with an integer N (0<N<4001) which denotes the total number of strings. Each of the next N lines contains one string. Strings contain only alphanumerals (‘0’… ‘9’, ‘A’… ‘Z’, ‘a’… ‘z’) have a maximum length of 1000, and a minimum length of 1.  

Input is terminated by a line containing a single zero. Input file size is around 23 MB.

Output

For each set of input produce one line of output. This line contains the serial of output followed by an integer T. This T denotes the total number of comparisons that are required in the strcmp() function if all the strings are compared with one another exactly once. So for N strings the function strcmp() will be called exactly 

 times. You have to calculate total number of comparisons inside the strcmp() function in those

 calls. You can assume that the value of T will fit safely in a 64-bit signed integer. Please note that the most straightforward solution (Worst Case Complexity O(N2 *1000)) will time out for this problem.

Sample Input                              Output for Sample Input

2 a b 4 cat hat mat sir

Case 1: 1 Case 2: 6

Problem Setter: Shahriar Manzoor, Special Thanks: Md. Arifuzzaman Arif, Sohel Hafiz, Manzurur Rahman Khan

參考了一下lrj的代碼，感覺左兒子右兄弟表示法相當好用，贊！

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>

using namespace std;
///#define Online_Judge
#define outstars cout << "***********************" << endl;
#define clr(a,b) memset(a,b,sizeof(a))
#define lson l , mid  , rt << 1
#define rson mid + 1 , r , rt << 1 | 1

#define mk make_pair
#define FOR(i , x , n) for(int i = (x) ; i < (n) ; i++)
#define FORR(i , x , n) for(int i = (x) ; i <= (n) ; i++)
#define REP(i , x , n) for(int i = (x) ; i > (n) ; i--)
#define REPP(i ,x , n) for(int i = (x) ; i >= (n) ; i--)
const int MAXN = 4000 * 1000 + 50;
const int sigma_size = 26;
const long long LLMAX = 0x7fffffffffffffffLL;
const long long LLMIN = 0x8000000000000000LL;
const int INF = 0x7fffffff;
const int IMIN = 0x80000000;
#define eps 1e-4
const int MOD = (int)1e9 + 7;
typedef long long LL;
const double PI = acos(-1.0);
typedef double D;
typedef pair<int , int> pi;
///#pragma comment(linker, "/STACK:102400000,102400000")
struct Trie
{
    int head[MAXN];/// head[i]為第i個結點的左兒子編号
    int next[MAXN];/// next[i]為第i個結點的右兄弟編号
    int tot[MAXN];/// ch[i]為第i個結點上的字元
    char ch[MAXN]; /// tot[i]為第i個結點為根的子樹包含的葉結點總數
    int sz; /// 結點總數
    LL ans;
    void clear()
    {
        sz = 1 , head[0] = next[0] = tot[0] = 0;
    }
    /// 插入字元串s（包括最後的'\0'），沿途更新tot
    void insert(char * s)
    {
        int u = 0 , v , n = strlen(s);
        tot[0] ++;
        FORR(i ,0 , n)
        {
            bool found = false;
            for(v = head[u] ; v != 0 ; 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] ++;
        }

    }
    /// 統計LCP=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 != 0 ; v = next[v])
            {
                sum += tot[v] * (tot[u] - tot[v]);/// 子樹v中選一個串，其他子樹中再選一個
            }
            ans += sum / 2 * (2 * depth + 1);/// 除以2是每種選法統計了兩次
            for(int v = head[u] ; v != 0 ; v = next[v])dfs(depth + 1 , v);
        }
    }
    LL count()
    {
        ans =0 ;
        dfs(0 , 0);
        return ans;
    }
};

char str[1010];
Trie trie;
int n;
int main()
{
    //ios::sync_with_stdio(false);
#ifdef Online_Judge
    //freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // Online_Judge
    int kase = 1;
    while(~scanf("%d" , &n) , n)
    {
        trie.clear();
        while(n--)
        {
            scanf("%s" ,str);
            trie.insert(str);
        }

        printf("Case %d: %lld\n" , kase++ , trie.count());
    }
    return 0;
}