Cod sursa(job #1719857)

Utilizator DjokValeriu Motroi Djok Data 20 iunie 2016 15:11:00
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<bits/stdc++.h>
using namespace std;

typedef struct state {
    int len,link,cnt;
    map<char,int> next;
}State;

int i,n,q,sz,last;
//vector<int> lens[1000005];
string s;
State sa[2000005];

void add_letter(char c) {
    int now=sz++,p;

    sa[now].len=sa[last].len+1; sa[now].cnt=1;
    //lens[sa[now].len].push_back(now);

    for(p=last;p!=-1 && !sa[p].next.count(c);p=sa[p].link) sa[p].next[c]=now;

    if(p==-1) sa[now].link=0;
    else {
           int q=sa[p].next[c];

           if(sa[q].len==sa[p].len+1) sa[now].link=q;
           else {
                  int clone=sz++;

                  sa[clone]=sa[q];
                  sa[clone].len=sa[p].len+1;
                  sa[clone].cnt=0;
      //            lens[sa[clone].len].push_back(clone);

                  for(;p!=-1 && sa[p].next[c]==q;p=sa[p].link) sa[p].next[c]=clone;

                  sa[now].link=sa[q].link=clone;
                }
         }

    last=now;
}

int Solve() {
    int now=0,i,n=s.length();

    for(i=0;i<n;++i)
     if(sa[now].next[s[i]]) now=sa[now].next[s[i]];
     else return 0;

    return sa[now].cnt;
}

int main()
{
  ifstream cin("ahocorasick.in");
  ofstream cout("ahocorasick.out");

  ios_base::sync_with_stdio(0);

  cin>>s; sz=1; sa[0].link=-1; n=s.length();
  for(i=0;i<n;++i) add_letter(s[i]);

 /* for(i=1e6;i;--i)
   for(auto it:lens[i])
    sa[sa[it].link].cnt+=sa[it].cnt;
*/
  for(cin>>q;q;--q) cin>>s,cout<<Solve()<<'\n';

 return 0;
}