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自动机