Cod sursa(job #2721949)

Utilizator victorzarzuZarzu Victor victorzarzu Data 12 martie 2021 14:48:41
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
char s[1000005], cuv[10005];
int n, st, sf, rez[100];

struct trie
{
  int nr;
  vector<int> ter;
  trie *fiu[26], *fail;

  trie()
  {
    nr = 0;
    memset(fiu, 0, sizeof(fiu));
    fail = NULL;
  }
};

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

void insert(trie *nod, char *s, int index)
{
  if(!(*s))
  {
    nod -> ter.push_back(index);
    return;
  }
  int urm = *s - 'a'
  if(!(nod -> fiu[urm]))
    nod -> fiu[urm] = new trie;
  insert(nod -> fiu[urm], s + 1, index);
}

void Read()
{
  f>>s;
  f>>n;
  for(int i = 1;i <= n;++i)
    f>>cuv, insert(T, cuv, i);
}

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

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

    for(short ch = 0;ch < 26;++ch)
      if(top -> fiu[ch])
      {
        for(fa = top -> fail;fa != T && !fa -> fiu[ch];fa = fa -> fail);
        if(fa -> fiu[ch] && fa -> fiu[ch] != top -> fiu[ch]) fa = fa -> fiu[ch];
        top -> fiu[ch] -> fail = fa;
        q[++sf] = top -> fiu[ch];
      }
  }
}

void reverse()
{
  trie *top;
  for(int i = sf;i > 0;--i)
  {
    top = q[i];
    if(top -> fail) top -> fail -> nr += top -> nr;
    for(auto it : top -> ter)
      rez[it] += top -> nr;
  }
}

void Solve()
{
  compute();
  U = T;
  for(int i = 0;i < strlen(s);++i)
  {
    int urm = s[i] - 'a';
    for(;U != T && !U -> fiu[urm];U = U -> fail);
    if(U -> fiu[urm]) U = U -> fiu[urm];
    U -> nr++;
  }
  reverse();
  for(int i = 1;i <= n;++i)
    g<<rez[i]<<'\n';
}

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