[二進制分組+AC自動機] HDU4787 GRE Words Revenge

GRE Words Revenge

題意：

一個01字元串機器，兩種操作：

• +String 表示增加String串進機器裡
• ？String 表示查詢String串有多少個子串在機器裡面

要求強制線上，給出的串要循環左移lastans次。lastans是上次查詢的答案。

思路：

若沒有增加操作，可以看出這是個AC自動機的裸題，于是就采用《淺談資料結構的幾個非經典解法》論文中說的二進制分組，巧妙的用一個log的代價暴力實作線上，複雜度證明還是沒看懂，不過跑得倒是挺快，代碼應該比較簡單，認真看看就明白了，其實就是開log個AC自動機，有點二項堆的意思，妙。

mdzz寫錯了循環位移wa了5發。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MBIT = ;
const int MX = +;
struct lowbit_trie{
    int son[MX][], end[MX], fail[MX];
    int root[MBIT], size[MBIT], bitcnt, alloc;
    string str[]; int scnt;
    set<string>st;
    void init(){
        alloc = scnt = bitcnt = ;
        memset(root, , sizeof(root));
        memset(size, , sizeof(size));
        st.clear();
    }
    int newnode(){
        memset(son[++alloc], , sizeof(son[alloc]));
        end[alloc] = fail[alloc] = ;
        return alloc;
    }
    void build(int rt){
        queue<int>q;
        fail[rt] = rt;
        for(int i = ; i < ; ++i){
            if(!son[rt][i]) son[rt][i] = rt;
            else fail[son[rt][i]] = rt, q.push(son[rt][i]);
        }
        while(!q.empty()){
            int u = q.front(); q.pop();
            end[u] += end[fail[u]];
            for(int i = ; i < ; ++i){
                if(!son[u][i]) son[u][i] = son[fail[u]][i];
                else fail[son[u][i]] = son[fail[u]][i], q.push(son[u][i]);
            }
        }
    }
    void rebuild(int l, int r, int &rt){
        rt = newnode();
        for(int i = l; i <= r; ++i){
            int p = rt;
            for(int j = ; j < str[i].length(); ++j){
                if(son[p][str[i][j]-'0'] == ) son[p][str[i][j]-'0'] = newnode();
                p = son[p][str[i][j]-'0'];
            }
            end[p]++;
        }
        build(rt);
    }
    void insert(char *s){
        if(st.count(s) == ) return;
        st.insert(s);
        str[++scnt] = string(s);
        size[++bitcnt] = , root[bitcnt] = newnode();
        while(bitcnt >=  && size[bitcnt] == size[bitcnt-]){
            size[--bitcnt] *= ;
        }
        alloc = root[bitcnt]-;
        rebuild(scnt-size[bitcnt]+, scnt, root[bitcnt]);
    }
    ll _query(char *s, int rt){
        int p = rt; ll res = ;
        for(int i = ; s[i]; ++i){
            p = son[p][s[i]-'0'];
            res += end[p];
        }
        return res;
    }
    ll query(char *s){
        ll res = ;
        for(int i = ; i <= bitcnt; ++i){
            res += _query(s, root[i]);
        }
        return res;
    }
}ac;
char tmp[];
char ss[];
void getss(ll k){
    scanf("%s", tmp);
    int len = strlen(tmp+);
    for(int i = ; i < len; ++i){
        ss[i] = tmp[+(i+k)%len];
    }
    ss[len] = '\0';
}
int main(){
    int T, ca = ;
    scanf("%d", &T);
    while(T--){
        int n; ll last = ;
        scanf("%d%*c", &n);
        ac.init();
        printf("Case #%d:\n", ca++);
        for(int i = ; i < n; ++i){
            getss(last);
            if(tmp[] == '+') ac.insert(ss);
            else printf("%lld\n", last = ac.query(ss));
        }
    }
}