Cod sursa(job #2931627)

Utilizator victorzarzuZarzu Victor victorzarzu Data 31 octombrie 2022 17:31:39
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>

#define N 1000005 

using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int n;
char str[N], cuv[10005];
int result[101];
int st, fn;

struct Trie {
  int number;
  vector<int> indices;
  Trie* children[26];
  Trie* fail;

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

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

void insert(Trie* node, char* word, int ind) {
  if(!isalpha(*word)) {
    node->indices.push_back(ind);
    return;
  }
  int next = *word - 'a';
  if(!(node->children[next])) {
    node->children[next] = new Trie;
  }
  insert(node->children[next], word + 1, ind);
}

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

void precompute() {
  Trie *top, *fa;
  T->fail = T;

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

    for(int next = 0;next < 26;++next) {
      if(top->children[next]) {
        for(fa = top->fail;fa != T && !(fa->children[next]);fa = fa->fail);
        if(fa->children[next] && fa->children[next] != top->children[next]) {
          fa = fa->children[next];
        }
        top->children[next]->fail = fa;
        q[++fn] = top->children[next];
      }
    }
  }
}

void compute() {
  Trie* top;

  for(int ind = fn;ind >= 1;--ind) {
    top = q[ind];

    if(top->fail) {
      top->fail->number += top->number;
    }
    for(const auto& index : top->indices) {
      result[index] += top->number;
    }
  }
}

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

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