Editorial for Bedao Grand Contest 05 - ANTI
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; struct data { int c[26]; bool eow; } eNode; struct dataX { int c[26]; vector <int> vec; } eNodeX; vector <data> nCoV; vector <dataX> SARS; void MERS(string s) { for (int i = 0; i < (int)s.size(); ++i) { int r = 0, l = min((int)s.size() - 1, i + 5); for (int j = i; j <= l; ++j) { int x = s[j] - 'a'; if (SARS[r].c[x] < 0) { SARS[r].c[x] = (int)SARS.size(); SARS.push_back(eNodeX); } r = SARS[r].c[x]; SARS[r].vec.push_back(i); } } } void ins(string s) { int j = 0; for (int i = (int)s.size() - 1; i >= 0; --i) { int x = s[i] - 'a'; if (nCoV[j].c[x] < 0) { nCoV[j].c[x] = (int)nCoV.size(); nCoV.push_back(eNode); } j = nCoV[j].c[x]; } nCoV[j].eow = 1; } dataX newNodeX() { dataX tmp; tmp.vec.clear(); for (int i = 0; i < 26; ++i) tmp.c[i] = -1; return tmp; } data newNode() { data tmp; tmp.eow = 0; for (int i = 0; i < 26; ++i) tmp.c[i] = -1; return tmp; } int antivirus(std::string header, std::vector<std::string> keywords, std::string code) { int ans = 0; eNode = newNode(); eNodeX = newNodeX(); nCoV.push_back(eNode); SARS.push_back(eNodeX); MERS(code); ins(header); for (int i = 0; i < (int)header.size(); ++i) { string tmp = header; tmp.erase(i, 1); ins(tmp); } for (int i = 1; i < (int)header.size(); ++i) { if (abs(header[i] - header[i - 1]) != 1) continue; string tmp = header; swap(tmp[i], tmp[i - 1]); ins(tmp); } for (int i = 0; i < (int)header.size(); ++i) for (int j = 97; j <= 97 + 25; ++j) { if (j == (int)header[i]) continue; string tmp = header; tmp[i] = (char)j; ins(tmp); } sort(keywords.begin(), keywords.end()); for (int i = 0; i < (int)keywords.size(); ++i) { bool ok = 0; if (i && keywords[i] == keywords[i - 1]) continue; int r = 0; for (int j = 0; j < (int)keywords[i].size() && !ok; ++j) if (SARS[r].c[keywords[i][j] - 'a'] < 0) ok = 1; else r = SARS[r].c[keywords[i][j] - 'a']; if (ok) continue; vector <int> position = SARS[r].vec; for (int pos: position) { if (ok) break; int k = pos - 1, j = 0; while (k >= 0 && pos - 1 - k + 1 <= (int)header.size() && !ok) { j = nCoV[j].c[code[k] - 'a']; if (j < 0) break; if (nCoV[j].eow) { ok = 1; ++ans; break; } --k; } } } return ans; } int main() { freopen("ANTI.INP", "r", stdin); freopen("ANTI.OUT", "w", stdout); string g, c, x; int n; vector <string> V; cin >> g >> n; for (int i = 1; i <= n; ++i) cin >> x, V.push_back(x); cin >> c; cout << antivirus(g, V, c); return 0; }
Comments