Trie with O(sigma * N / W) space. hdu5880

memory_friendly_trie.cc

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int M = 400005;
const int SIGMA = 26;

int pct[1 << 13];
inline int popcount(int x) {
    return pct[x >> 13] + pct[x & 8191];
}

int m;
char text[N];
char* s[N];
int len[N];

int Next[N];
int pre[M];


int nodecnt;
int mask[M] , from[M] , f[M] , val[M];

void init() {
    int total_len = 0;
    scanf("%d" , &m);
    for (int i = 0 ; i < m ; ++ i) {
        s[i] = text + total_len;
        scanf("%s\n" , s[i]);
        len[i] = strlen(s[i]);
        total_len += len[i] + 1;
    }
    for (int i = 1 ; i < 1 << 13 ; ++ i) {
        pct[i] = pct[i & (i - 1)] + 1;
    }
}

#define has(u , v) (mask[(u)] >> (v) & 1)
#define go(u , v) (from[(u)] + popcount(mask[(u)] & ((1 << (v)) - 1)))
void build() {
    nodecnt = 1;
    pre[0] = -1;
    mask[0] = 0;
    for (int i = 0 ; i < m ; ++ i) {
        Next[i] = pre[0];
        pre[0] = i;
        mask[0] |= 1 << *s[i] - 'a';
    }
    static int que[N];
    int top = 0 , bot = -1;
    que[++ bot] = 0;

    while (top <= bot) {
        int x = que[top ++];
        from[x] = nodecnt;
        int childcnt = popcount(mask[x]);
        //cout << x << ' ' << childcnt << endl;
        for (int i = 0 ; i < childcnt ; ++ i) {
            pre[nodecnt] = -1;
            mask[nodecnt] = 0;
            val[nodecnt] = 0;
            nodecnt ++;
        }

        int exist = mask[x];
        for (int k = pre[x] , nxt ; ~k ; k = nxt) {
            int c = *(s[k] ++) - 'a';
            int y = go(x , c);
            if (exist >> c & 1) {
                exist ^= 1 << c;
                int j = f[x];
                while (j && !has(j , c)) {
                    j = f[j];
                }
                f[y] = has(j , c) && x != 0 ? go(j , c) : 0;
                val[y] = max(val[y] , val[f[y]]);
                que[++ bot] = y;
            }
            nxt = Next[k];
            if (*s[k]) {
                mask[y] |= 1 << *s[k] - 'a';
                Next[k] = pre[y];
                pre[y] = k;
            } else {
                val[y] = max(val[y] , len[k]);
            }
        }
    }
}
char str[N];
int sum[N];
void work() {
    fgets(str , N , stdin);
    int Len = strlen(str);
    while (Len && str[Len - 1] == '\n') {
        str[-- Len] = 0;
    }
    memset(sum , 0 , sizeof(*sum) * (Len + 1));
    int x = 0;
    for (int i = 0 ; i < Len ; ++ i) {
        if (isalpha(str[i])) {
            int c = tolower(str[i]) - 'a';
            while (x && !has(x , c)) {
                x = f[x];
            }
            x = has(x , c) ? go(x , c) : 0;
        } else {
            x = 0;
        }
        ++ sum[i - val[x] + 1];
        -- sum[i + 1];
    }
    for (int i = 0 ; i < Len ; ++ i) {
        if (sum[i] > 0) {
            str[i] = '*';
        }
        sum[i + 1] += sum[i];
    }
    puts(str);
}


int main() {
    int T;
    scanf("%d" , &T);
    while (T --) {
        init();
        build();
        work();
    }
}