Detect the Virus

题意是真恶心!!!!!!!!
但还好,锻炼了编码的能力。

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int max_n = 550;
const int max_m = 3000 * 8;
struct AC_Automation {
    int teir[max_n * 65][300];
    int fail[max_n * 65];
    int is[max_n * 65];
    bool vis[max_n * 65];
    int cnt = 0;
    int tot = 0;
    void init() {
        memset(teir, 0, sizeof(teir));
        memset(fail, 0, sizeof(fail));
        memset(is, 0, sizeof(is));
        cnt = tot = 0;
    }void insert(int* p, int n) {
        int cur = 0;
        for (int i = 0;i < n;++i) {
            if (teir[cur][p[i]] == 0)
                teir[cur][p[i]] = ++cnt;
            cur = teir[cur][p[i]];
        }is[cur]++;
    }void build() {
        queue<int> que;
        for (int i = 0;i < 300;++i)
            if (teir[0][i] != 0)
                que.push(teir[0][i]);
        while (!que.empty()) {
            int u = que.front();que.pop();
            for (int i = 0;i < 300;++i)
                if (teir[u][i] != 0) {
                    fail[teir[u][i]] = teir[fail[u]][i];
                    que.push(teir[u][i]);
                }
                else teir[u][i] = teir[fail[u]][i];
        }
    }int quiry(int* s, int n) {
        memset(vis, false, sizeof(vis));
        int cur = 0;int ans = 0;
        for (int i = 0;i < n;++i) {
            cur = teir[cur][s[i]];
            for (int j = cur;j && !vis[j];j = fail[j]) {
                ans += is[j];
                vis[j] = true;
            }
        }return ans;
    }
}ac;
char p[max_m];
int pp[max_m];
int N, M;
char h[65] = { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" };
int Toint(char c) {
    for (int i = 0;i <= 64;++i)
        if (h[i] == c)
            return i;
}
int vary() {
    int n = strlen(p);
    vector<int> ss;
    for (int i = 0;i < n && p[i] != '=';++i) {
        int t = Toint(p[i]);
        for (int j = 5;j >= 0;--j)
            ss.push_back((t>>j) & 1);
    }int k = 0;
    for (int i = 0;i + 7 < ss.size();i += 8) {
        int t = 0;
        for (int j = 0;j <= 7;++j)
            if (ss[i + j] == 1)
                t += (1 << (7 - j));
        pp[k++] = t;
    }return k;
}
int main() {
    ios::sync_with_stdio(0);
    while (cin >> N) {
        ac.init();
        while (N--) {
            cin >> p;
            int len = vary();
            ac.insert(pp, len);
        }ac.build();
        cin >> M;
        while (M--) {
            cin >> p;
            int len = vary();
            cout << ac.quiry(pp, len) << endl;
        }cout << endl;
    }
}
Kuangbin刷题详解(AC自动机) 文章被收录于专栏

AC自动机

全部评论

相关推荐

头像
11-09 17:30
门头沟学院 Java
TYUT太摆金星:我也是,好几个华为的社招找我了
点赞 评论 收藏
分享
10-09 09:39
门头沟学院 C++
HHHHaos:这也太虚了,工资就一半是真的
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务