ZOJ 3430 Detect the Virus 【AC自动机+解码】

解码的那些事儿，不多说。

注意解码后的结果各种情况都有，用整数数组存储，char数组会超char类型的范围（这个事最蛋疼的啊）建立自动机的时候不能用0来判断结束。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#include <string>

#include <iostream>

using namespace std;

vector<int> ans;

struct AC_Automata {

    #define N 60010

    #define M 256

    int ch[N][M], sz;

    int val[N], last[N], f[N], cc[N];

    void clear() {

        sz = 1;

        memset(ch[0], 0, sizeof(ch[0]));

    }

    void insert(int s[], int l, int v) {

        int u = 0;

        for (int i=0; i<l; i++) {

            int c = s[i];

            if (!ch[u][c]) {

                memset(ch[sz], 0, sizeof(ch[sz]));

                val[sz] = 0;

                ch[u][c] = sz++;

            }

            u = ch[u][c];

        }

        val[u] = v;

    }

    void build() {

        queue<int> q;

        f[0] = 0;

        for (int c=0; c<M; c++) {

            int u = ch[0][c];

            if (u) { f[u] = last[u] = 0; q.push(u); }

        }

        while (!q.empty()) {

            int r = q.front(); q.pop();

            for (int c=0; c<M; c++) {

                int u = ch[r][c];

                if (!u) { ch[r][c] = ch[f[r]][c]; continue; }

                q.push(u);

                f[u] = ch[f[r]][c];

                last[u] = val[f[u]] ? f[u] : last[f[u]];

            }

        }

    }

    void find(int s[], int l) {

        int j = 0;

        for (int i=0; i<l; i++) {

            int c = s[i];

            j = ch[j][c];

            if (val[j]) print(j);

            else if (last[j]) print(last[j]);

        }

    }

    void print(int j) {

        if (j) {

            ans.push_back(val[j]);

            print(last[j]);

        }

    }

} ac;

int get(char c) {

    if (c >= 'A' && c <= 'Z') return c-'A';

    if (c >= 'a' && c <= 'z') return c-'a'+26;

    if (c >= '0' && c <= '9') return c-'0'+ 52;

    if (c == '+') return 62;

    return 63;

}

int ss[30002];

int bit[30003*10];

int decode(char str[]) {

    int top = 0;

    int a[10];

    for(int i=0; str[i]; i++) {

        if(str[i]!='='){

            int x = get(str[i]);

            for(int j=5;j>=0;j--){

                a[j] = x & 1;

                x >>= 1;

            }

            for (int j=0; j<6; j++) bit[top++] = a[j];

        }else

            top -= 2;

    }

    int x = 0;

    int tot = 0;

    for(int i=0;i<top;){

        x = 0;

        for(int j=0;j<8;j++)

            x = x<<1 | bit[i++];

        ss[tot++] = x;

    }

    return tot;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

#endif

    int n, m;

    char s[30023];

    while (scanf(" %d", &n) == 1) {

        ac.clear();

        for (int i=1; i<=n; i++) {

            scanf(" %s", s);

            int l = decode(s);

            ac.insert(ss, l, i);

        }

        ac.build();

        scanf(" %d", &m);

        while (m--) {

            ans.clear();

            scanf(" %s", s);

            int l = decode(s);

            ac.find(ss, l);

            sort(ans.begin(), ans.end());

            int cnt = unique(ans.begin(), ans.end()) - ans.begin();

            printf("%d\n", cnt);

        }

        puts("");

    }

    return 0;

}

巴特西

ZOJ 3430 Detect the Virus 【AC自动机+解码】

最新文章

热门文章