Cod sursa(job #2806134)

Utilizator victorzarzuZarzu Victor victorzarzu Data 22 noiembrie 2021 13:23:20
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
#define mod 666013

using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
char sentence[1000005], word[10005];
int n, st, fin, rez[10005];

struct trie{
  int number;
  vector<int> indices;
  trie *children[26], *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 compute()
{
  trie *top, *fa;
  T -> fail = T;

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

    for(int ch = 0;ch < 26;++ch)
      if(top -> children[ch])
        {
          for(fa = top -> 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 reverse()
{
  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)
      rez[it] += top -> number;
  }
}

void solve()
{
  compute();
  U = T; int len = strlen(sentence);
  for(int i = 0;i < len;++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++;
  }
  reverse();
  for(int i = 1;i <= n;++i)
    g<<rez[i]<<'\n';
  f.close();
  g.close();
}

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

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