hdu - 3460 - Ancient Printer

題意：給出N個由小寫字母組成的隊名，用一台古老的打印機這些隊名打印出來，問最少要敲幾次鍵盤（隊名之間不用按輸入順序），這台打印機只能執行以下3種操作：

1.在現有基礎上的末尾繼續輸入小寫字母；

2.刪除最後一個字母；

3.打印現有串。

（1 <= N <= 10000, 隊名長度 <= 50）

——>>組織好Trip，記錄總結點數sz，每個結點到根結點的距離，得到距離根結點最遠的結點的距離Max，那麼答案為2 * sz + N - Max。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxw = 50 + 10;
int N;
char name[maxw];

struct node{
    int dis;
    node *next[26];
    node(){
        dis = 0;
        memset(next, 0, sizeof(next));
    }
};

struct Trip{
    node *root;
    int Max;
    int sz;

    Trip(){
        root = new node;
        Max = -1;
        sz = 0;
    }

    int idx(char c){
        return c - 'a';
    }

    void insert(char *s){
        node *t = root;
        int len = strlen(s), i;
        for(i = 0; i < len; i++){
            int c = idx(s[i]);
            if(!t->next[c]){
                t->next[c] = new node;
                sz++;
            }
            t->next[c]->dis = t->dis + 1;
            t = t->next[c];
        }
        Max = max(Max, t->dis);
    }

    void solve(){
        printf("%d\n", 2 * sz + N - Max);
    }
};

int main()
{
    while(scanf("%d", &N) == 1){
        Trip trip;
        for(int i = 0; i < N; i++){
            scanf("%s", name);
            trip.insert(name);
        }
        trip.solve();
    }
    return 0;
}