Cod sursa(job #2440285)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 18 iulie 2019 02:27:01
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#include <vector>
using namespace std;

struct nod
{
  int cnt;
  vector<int> id;
  nod* back;
  nod* son['z'-'a'+1]={0};
};

char c[1005000];
char v[150][10500];
int countt[150];
nod * root;
int n,t;
nod * q[10500*150];

void insert( char * p, nod * nd, int i)
{
  if((*p)=='\0')
  {
    nd->id.push_back(i);
    return;
  }
  if(nd->son[(*p)-'a']==0)
    nd->son[(*p)-'a']= new nod;
  insert(p+1,nd->son[(*p)-'a'],i);
}

int main()
{	
  freopen("ahocorasick.in","r",stdin);
	freopen("ahocorasick.out","w",stdout);
	scanf("%s",c);
	scanf("%d",&n);
  root= new nod;
  root->back= root;
  for(int i=0;i<n;i++)
  {
    scanf("%s",v[i]);
    insert(v[i],root,i);
  }
 /* q[0]=root;
  for(int i=0;i<=t;++i)
  {
    nod * tp= q[i];
    for(int i=0;i<='z'-'a';i++)
    {
      nod * u = tp->son[i];
      if(u!=0)
      {
        nod *nd= tp->back;
        while( nd!=root &&nd->son[i]==0)
          nd= nd->back;
        if(nd->son[i]!=0 && nd->son[i]!=u)
          nd=nd->son[i];
        u->back= nd;
        t++;
        q[t]=u;
      }
    }
  }
  root->back=0;
  nod *nd= root;
  for(int i=0;c[i]!='\0';i++)
  {
    int ch = c[i]-'a';
    while(nd->son[ch]==0 && nd!=root) nd= nd->back;
    if(nd->son[ch]!=0)
      nd=nd->son[ch];
    (nd->cnt)++;
  }
  
  for(int i=t;i>0;i--)
  {
    nod * u =q[i];
    for(int it= 0;it!=u->id.size();++it )
      countt[u->id[it]]+=u->cnt;
    u->back->cnt+=u->cnt;
  }*/
  for(int i=0;i<n;i++)
    printf("%d\n",countt[i]);
}