poj 2001 Shortest Prefixes(字典樹)

poj 2001 Shortest Prefixes(字典樹)

題目鏈接：poj 2001 Shortest Prefixes

題目大意：給定一個字符串集合，要求使得每個字符串盡量縮短，但是仍然能區分開。

解題思路：根據字符串集建立字典樹，並且每插入一個字符串，所有路徑上節點均加1，表示該子串是這個字符串的前

綴。然後對每個字符串進行一次查找，當碰到節點的統計值為1時，表示當前子串僅為該字符串的前綴，即為要找的字

符串。

#include 
#include 
#include 

using namespace std;

const int maxn = 20005;
const int sigma_size = 26;

struct Tire {
    int sz;
    int g[maxn][sigma_size];
    int val[maxn];

    void init();
    int idx(char ch);
    void insert(char* s);
    void find(char* s);
}T;

int N;
char w[1005][25];

int main () {
    N = 0;
    T.init();

    while (scanf("%s", w[N]) == 1)
        T.insert(w[N++]);

    for (int i = 0; i < N; i++) {
        printf("%s ", w[i]);
        T.find(w[i]);
        printf("\n");
    }
    return 0;
}

void Tire::init() {
    sz = 1;
    val[0] = 0;
    memset(g[0], 0, sizeof(g[0]));
}

int Tire::idx (char ch) {
    return ch - 'a';
}

void Tire::find(char* s) {
    int u = 0, n = strlen(s);

    for (int i = 0; i < n; i++) {
        int v = idx(s[i]);

        u = g[u][v];
        printf("%c", s[i]);
        if (val[u] == 1)
            return;
    }
}

void Tire::insert(char* s) {
    int u = 0, n = strlen(s);

    for (int i = 0; i < n; i++) {
        int v = idx(s[i]);

        if (g[u][v] == 0) {
            val[sz] = 0;
            memset(g[sz], 0, sizeof(g[sz]));
            g[u][v] = sz++;
        }

        u = g[u][v];
        val[u]++;
    }
}