Cod sursa(job #3148037)

Utilizator vladburacBurac Vlad vladburac Data 29 august 2023 00:55:07
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
using namespace std;
const int MAXNODES = 1e6 + 2;
const int MAXEDGES = 26;
const int NMAX = 100;

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

bitset <100> endingWords[MAXNODES+1];
int state[MAXNODES+1][MAXEDGES+1];
int root, nrStates;
string words[NMAX+1];
int fail[MAXNODES+1];
int ans[NMAX+1];

void addWord( int ind ) {
  int i, curState;
  curState = root;
  for( i = 0; i < words[ind].size(); i++ ) {
    if( state[curState][words[ind][i]-'a'] == 0 )
      state[curState][words[ind][i]-'a'] = nrStates++;
    curState = state[curState][words[ind][i]-'a'];
  }
  endingWords[curState][ind] = 1;
}

void bfs() {
  int i, curState;
  queue <int> q;
  for( i = 0; i < MAXEDGES; i++ ) {
    if( state[root][i] ) {
      q.push( state[root][i] );
      fail[state[root][i]] = root;
    }
  }
  while( !q.empty() ) {
    auto qfront = q.front();
    q.pop();
    for( i = 0; i < MAXEDGES; i++ ) {
      if( state[qfront][i] ) {
        q.push( state[qfront][i] );
        curState = qfront;
        do {
          curState = fail[curState];
          if( state[curState][i] ) {
            fail[state[qfront][i]] = state[curState][i];
            endingWords[state[qfront][i]] |= endingWords[fail[state[qfront][i]]];
            break;
          }
          else if( curState == root )
            fail[state[qfront][i]] = root;
        } while( curState != root );

      }
    }
  }
}

string s;
int n;
void goThroughString() {
  int i, curState, j;
  curState = root;
  for( i = 0; i < s.size(); i++ ) {
    while( state[curState][s[i]-'a'] == 0 && curState != root )
      curState = fail[curState];
    if( state[curState][s[i]-'a'] != 0 )
      curState = state[curState][s[i]-'a'];
    if( !endingWords[curState].any() )
      continue;
    j = endingWords[curState]._Find_next(-1);
    /*for( j = 0; j < n; j++ ) {
      if( endingWords[curState][j] )
        ans[j]++;
    }*/
    while( j != 100 ) {
      ans[j]++;
      j = endingWords[curState]._Find_next(j);
    }
  }
}

int main() {
  int i;
  fin >> s;
  root = 1;
  nrStates = 2;
  fin >> n;
  for( i = 0; i < n; i++ ) {
    fin >> words[i];
    addWord( i );
  }
  bfs();
  goThroughString();
  for( i = 0; i < n; i++ )
    fout << ans[i] << "\n";
  return 0;
}