Cod sursa(job #2357685)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 27 februarie 2019 17:30:03
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

#define ll long long
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100;
int const sigma = 26;

struct Trie{
  int val;
  int scount;
  Trie* son[sigma];
  Trie* failure;
  Trie(){
    val = scount = 0;
    for(int i = 0; i < sigma; i++)
      son[i] = nullptr;
    failure = nullptr;
  }
};
Trie* root;

void addtrie(Trie* &node, string &s, int pos, int code){
  if(pos == s.size()) {
    node->val = code;
    return ;
  } else {
    if(node->son[s[pos] - 'a'] == nullptr)
      node->son[s[pos] - 'a'] = new Trie();
    addtrie(node->son[s[pos] - 'a'], s, pos + 1, code);
  }
}
void addFailure(Trie* &node, string &s, int pos, int code){
  if(pos == s.size()) {
    return ;
  } else {
    if(node->son[s[pos] - 'a'] == nullptr)
      node->son[s[pos] - 'a'] = new Trie();

    Trie* &newnode = node->son[s[pos] - 'a'];
    if(newnode->failure == nullptr){
      newnode->failure = node->failure;
      if(0 < pos){
        while(root != newnode->failure && newnode->failure->son[s[pos] - 'a'] == nullptr)
          newnode->failure = newnode->failure->failure;
        if(newnode->failure->son[s[pos] - 'a'] == nullptr)
          newnode->failure = root;
        else
          newnode->failure = newnode->failure->son[s[pos] - 'a'];
      }
    }
    addFailure(newnode, s, pos + 1, code);
  }
}
void explore(Trie* &node, char ch){
  while(root != node && node->son[ch - 'a'] == nullptr)
    node = node->failure;
  if(node->son[ch - 'a'] != nullptr)
    node = node->son[ch - 'a'];
  else
    node = root;
}

string s[5 + nmax];

bool compare(int x,int y){
  return s[x].size() < s[y].size();
}
int sol[5 + nmax];

vector<Trie*> order;

void bfs(Trie* node){
  queue<Trie*> q;
  q.push(node);
  while(0 < q.size()){
    node = q.front();
    q.pop();
    for(int h = 0; h < sigma; h++)
      if(node->son[h] != nullptr){
        q.push({node->son[h]});
        order.push_back(node->son[h]);
      }
  }
}

string printsequence;


int main()
{
  root = new Trie();
  root->failure = root;
  string original;
  int n;
  in >> original >> n;
  for(int i = 1;i <= n; i++)
    in >> s[i];

  for(int i = 1; i <= n; i++)
    addtrie(root, s[i], 0, i);
  for(int i = 1;i <= n; i++)
    addFailure(root, s[i], 0, i);

  Trie* currentpos = root;
  for(int i = 0; i < original.size(); i++) {
    explore(currentpos, original[i]);
    currentpos->scount++;
  }

  bfs(root);
  for(int i = order.size() - 1;0 <= i;i--){
    order[i]->failure->scount += order[i]->scount;
    sol[order[i]->val] = order[i]->scount;
  }

  for(int i = 1;i <= n;i++)
    out << sol[i] << '\n';

  return 0;
}