Cod sursa(job #2808096)

Utilizator victorzarzuZarzu Victor victorzarzu Data 24 noiembrie 2021 16:23:33
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
#define n_max 100000

using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
char sentence[10000001], w[10001];
int result[10001];
int st, fin, n;

struct trie{
  int number;
  vector<int> indices;
  trie *children['z' - 'a' + 1], *fail;

  trie()
  {
    number = 0;
    memset(children, 0, sizeof(children));
    fail = NULL;
  }
};

trie *T = new trie, *U = new trie;
trie *q[10000 * 10000 + 5];

void insert(trie *node, char *s, int index)
{
  if(!isalpha(*s))
  {
    node -> indices.push_back(index);
    return;
  }
  int next = *s - 'a';

  if(!node -> children[next])
    node -> children[next] = new trie;
  insert(node -> children[next], s + 1, index);
}

void read()
{
  f>>sentence;
  f>>n;
  for(int i = 1;i <= n;++i)
    f>>w, insert(T, w, i);
}

void compose()
{
  trie *fa, *top;
  T -> fail = T;

  for(q[st = fin = 1] = T;st <= fin;++st)
  {
    top = q[st];

    for(int ch = 0;ch <= 'z' - 'a';++ch)
      if(top -> children[ch])
      {
        for(fa = T -> fail;fa != T && !fa -> children[ch];fa = fa -> fail);
        if(fa -> children[ch] && fa -> children[ch] != top -> children[ch]) fa = fa -> children[ch];

        top -> children[ch] -> fail = fa;
        q[++fin] = top -> children[ch];
      }
  }
}

void calculate()
{
  trie *top;

  for(int i = fin;i >= 1;--i)
  {
    top = q[i];

    if(top -> fail) top -> fail -> number += top -> number; 

    for(auto it : top -> indices)
      result[it] += top -> number;
  }
}

void solve()
{
  compose();
  U = T;
  for(int i = 0;i < strlen(sentence);++i)
    {
      int next = sentence[i] - 'a';
      while(U != T && !U -> children[next]) U = U -> fail;
      if(U -> children[next])
        U = U -> children[next];
      U -> number++;
    }
  calculate();
  for(int i = 1;i <= n;++i)
    g<<result[i]<<'\n';
}


int main()
{
  read();
  solve();
  return 0;
}