Cod sursa(job #2313284)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 6 ianuarie 2019 16:19:05
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.85 kb
// By Stefan Radu

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <map>
#include <set>

using namespace std;

#define sz(x) (int)(x).size ()

typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

ifstream cin ("ahocorasick.in");
ofstream cout ("ahocorasick.out");

class Aho {
public:

  Aho () {

    root = new Node ();
    cin >> s >> n;
    coresp.resize (n);

    for (int i = 0; i < n; ++ i) {

      string aux;
      cin >> aux;

      coresp[i] = this -> mAdd (aux);
    }

    this -> mSetLinks();
  }

   void Solve () {

     auto curNode = root;

     for (int i = 0; i < sz (s); ++ i) {

        while (curNode != root) {
          if (curNode -> nxt[s[i] - 'a']) break;
          curNode = curNode -> sLink;
        }

        if (curNode -> nxt[s[i] - 'a']) {
          curNode = curNode -> nxt[s[i] - 'a'];
          ++ curNode -> frecv;
        }
     }

     while (not stk.empty ()) {

        curNode = stk.top ();
        stk.pop ();

        curNode -> sLink -> frecv += curNode -> frecv;
     }

     for (int i = 0; i < n; ++ i) {
        cout << coresp[i] -> frecv << '\n';
     }
   }

private:

  struct Node {

    Node () {
      this -> frecv = 0;
      this -> sLink = nullptr;
      for (int i = 0; i < 26; ++ i) this -> nxt[i] = nullptr;
    }

    int frecv;
    Node *nxt[26], *sLink;
  };

  int n;
  string s;
  Node *root;
  stack < Node* > stk;
  vector < Node* > coresp;

  Node* mAdd (string s) {

    Node* cur = root;

    for (int i = 0; i < sz (s); ++ i) {

      if (not cur -> nxt[s[i] - 'a']) {
          cur -> nxt[s[i] - 'a'] = new Node ();
      }

      cur = cur -> nxt[s[i] - 'a'];
    }

    return cur;
  }

  void mSetLinks () {

    queue < Node* > q;
    root -> sLink = root;

    for (int i = 0; i < 26; ++ i) {
      if (not root -> nxt[i]) continue;
      root -> nxt[i] -> sLink = root;
      q.push (root -> nxt[i]);
    }

    while (not q.empty ()) {

      auto curNode = q.front ();
      stk.push (curNode);
      q.pop ();

      for (int i = 0; i < 26; ++ i) {

        if (not curNode -> nxt[i]) continue;

        auto sLink = curNode -> sLink;
        while (sLink != root) {
          if (sLink -> nxt[i]) break;
          sLink = sLink -> sLink;
        }

        if (sLink -> nxt[i]) {
          curNode -> nxt[i] -> sLink = sLink -> nxt[i];
        }
        else {
          curNode -> nxt[i] -> sLink = root;
        }

        q.push (curNode -> nxt[i]);
      }
    }
  }
};

int main () {

  Aho *aC = new Aho ();
  aC -> Solve ();
}