Cod sursa(job #1122589)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 februarie 2014 19:02:20
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 5.02 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Automaton {
  public:
    static const int NIL = -1;

    Automaton(const int _sigma = 0, const int _v = 0, const int _start = NIL):
      sigma(_sigma),
      v(_v),
      start(_start),
      delta(vector< vector<int> >(_v, vector<int>(_sigma, NIL))),
      terminal(vector<bool>(_v, false)) {}

    int Size() const {
        return v;
    }

    int Sigma() const {
        return sigma;
    }

    int Start() const {
        return start;
    }

    int Delta(const int x, const int symbol) const {
        return delta[x][symbol];
    }

    bool IsTerminal(const int x) const {
        return terminal[x];
    }

    vector<int> GetTerminal() const {
        vector<int> terminalStates;
        for (int x = 0; x < v; ++x)
            if (terminal[x])
                terminalStates.push_back(x);
        return terminalStates;
    }

    void SetTerminal(const int x) {
        terminal[x] = true;
    }

    int AddVertex() {
        delta.push_back(vector<int>(sigma, NIL));
        terminal.push_back(false);
        return v++;
    }

    void AddEdge(const int from, const int to, const int symbol) {
        delta[from][symbol] = to;
    }

  protected:
    int sigma, v, start;
    vector< vector<int> > delta;
    vector<bool> terminal;
};

class AhoCorasickAutomaton: public Automaton {
  public:
    AhoCorasickAutomaton(const int _sigma, const vector< vector<int> > &signatures):
      Automaton(_sigma, 1, 0),
      signatureCount(int(signatures.size())),
      pi(vector<int>(1, 0)),
      signatureIndices(vector< vector<int> >(1, vector<int>())),
      processingOrder(vector<int>()) {
        for (int i = 0, x; i < int(signatures.size()); ++i) {
            x = start;
            for (int j = 0; j < int(signatures[i].size()); x = delta[x][signatures[i][j++]]) {
                if (delta[x][signatures[i][j]] == NIL) {
                    AddEdge(x, AddVertex(), signatures[i][j]);
                    pi.push_back(0);
                    signatureIndices.push_back(vector<int>());
                }
            }
            signatureIndices[x].push_back(i);
        }
        queue<int> q;
        for (q.push(start); !q.empty(); q.pop()) {
            int x = q.front();
            processingOrder.push_back(x);
            for (int symbol = 0; symbol < sigma; ++symbol) {
                int currentPi = pi[x];
                for (; currentPi != start && delta[currentPi][symbol] == NIL; currentPi = pi[currentPi]);
                if (delta[currentPi][symbol] != NIL && delta[currentPi][symbol] != delta[x][symbol])
                    currentPi = delta[currentPi][symbol];
                if (delta[x][symbol] == NIL) {
                    delta[x][symbol] = currentPi;
                } else {
                    pi[delta[x][symbol]] = currentPi;
                    q.push(delta[x][symbol]);
                }
            }
        }
        reverse(processingOrder.begin(), processingOrder.end());
    }

    vector<int> GetFrequencies(const vector<int> &stringToSearch) const {
        vector<int> signatureFrequencies = vector<int>(signatureCount, 0), vertexFrequencies = vector<int>(v, 0);
        for (int i = 0, x = start; i < int(stringToSearch.size()); ++i)
            ++vertexFrequencies[x = delta[x][stringToSearch[i]]];
        for (int i = 0; i + 1 < v; ++i)
            vertexFrequencies[pi[processingOrder[i]]] += vertexFrequencies[processingOrder[i]];
        for (int x = 0; x < v; ++x)
            for (vector<int>::const_iterator index = signatureIndices[x].begin(); index != signatureIndices[x].end(); ++index)
                signatureFrequencies[*index] += vertexFrequencies[x];
        return signatureFrequencies;
    }

  private:
    int signatureCount;
    vector<int> pi;
    vector< vector<int> > signatureIndices;
    vector<int> processingOrder;
};

string String;
vector<string> Signatures;
vector<int> Frequence;

void Solve() {
    vector< vector<int> > signatures = vector< vector<int> >(int(Signatures.size()), vector<int>());
    for (int i = 0; i < int(Signatures.size()); ++i)
        for (int j = 0; j < int(Signatures[i].size()); ++j)
            signatures[i].push_back(int(Signatures[i][j] - 'a'));
    AhoCorasickAutomaton A = AhoCorasickAutomaton(26, signatures);
    vector<int> stringToSearch;
    for (int i = 0; i < int(String.size()); ++i)
        stringToSearch.push_back(int(String[i] - 'a'));
    Frequence = A.GetFrequencies(stringToSearch);
}

void Read() {
    ifstream cin("ahocorasick.in");
    int n;
    cin >> String >> n;
    Signatures = vector<string>(n, "");
    for (int i = 0; i < n; ++i)
        cin >> Signatures[i];
    cin.close();
}

void Print() {
    ofstream cout("ahocorasick.out");
    for (int i = 0; i < int(Signatures.size()); ++i)
        cout << Frequence[i] << "\n";
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}