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.

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

Please read the guidelines before commenting.


There are no comments at the moment.