hdu - 3724 - Encoded Barcodes

題意：有N個產品，名稱由小寫字母組成，有M個詢問，每個詢問先來一個K，再輸入K個條形碼，每個條形碼代表1個小寫字母，這K個條形碼連成連續的K個字母作為前綴，統計這個前綴是多少個產品名的前綴（重復的算多次），輸出M個詢問的統計個數和（1 <= N <= 10000, 1 <= M <= 2000, 0 < K <= 30, 產品名長度 <= 30）。
 

——>>組織好Trip後，把條形碼轉換為小寫字母（大於平均值的為1，否則為0，計算ASCII碼），連成串，在Trip查找，求和。

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 30 + 5;
const int maxb = 8 + 5;
int N, M, K, bit[maxb];
double bar[maxb];
char qus[maxn];

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

struct Trip{
    node *root;
    int ret;

    Trip(){
        root = new node;
        ret = 0;
    }

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

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

    void solve(){
        node *t = root;
        int len = strlen(qus), i;
        for(i = 0; i < len; i++){
            int c = idx(qus[i]);
            if(!t->next[c]) break;
            t = t->next[c];
        }
        if(i == len) ret += t->cnt;
    }

    void print(){
        printf("%d\n", ret);
    }
};

int main()
{
    char product[maxn];
    int i, j, k;
    while(scanf("%d%d", &N, &M) == 2){
        Trip trip;
        for(i = 0; i < N; i++) {
            scanf("%s", product);
            trip.insert(product);
        }
        for(i = 0; i < M; i++){
            int cnt = 0;
            scanf("%d", &K);
            for(j = 0; j < K; j++){
                double sum = 0;
                for(k = 0; k < 8; k++){
                    scanf("%lf", &bar[k]);
                    sum += bar[k];
                }
                sum /= 8;
                int ASCII = 0;
                for(k = 0; k < 8; k++) if(bar[k] > sum) ASCII += (1 << (7-k));
                qus[cnt++] = (char)ASCII;
            }
            qus[cnt] = '\0';
            trip.solve();
        }
        trip.print();
    }
    return 0;
}