题意是真恶心!!!!!!!!
但还好,锻炼了编码的能力。
代码:
#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;
}
}
京公网安备 11010502036488号