Cod sursa(job #1316771)

Utilizator BologaDragosBologa Dragos BologaDragos Data 14 ianuarie 2015 08:54:08
Problema Aho-Corasick Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("ahocorasick.in") ;
ofstream g("ahocorasick.out") ;

char T[1000002] ;

char P[10005],c ;

int  L[10005] ;

int m,n,k,ct ;

int KMP()
{
    int p,t ;
    ct=0 ;
    k=0 ;
    L[1]=0 ;L[2]=0 ;
    for(p=2;p<=m;p++)
    {
        while(k>0&&P[k]!=P[p-1])
            k=L[k] ;
        if(P[k]==P[p-1])
            k++ ;
        L[p]=k ;
    }
    k=0 ;
    for(t=1;t<=n;t++)
    {
        while(k>0&&P[k]!=T[t-1])
            k=L[k] ;
        if(P[k]==T[t-1])
            k++ ;
        if(k==m)
        {
            ct++ ;
            //g<<t-m+1<<'\n';
            k=L[k] ;
        }
    }

    g<<ct<<'\n' ;

}

int main()
{
    int p,t,x,i ;

    f.getline(T,sizeof(T)) ;
    n=strlen(T) ;
    f>>x ;f.get() ;
    for(i=1;i<=x;i++)
    {
        f.getline(P,sizeof(P)) ;
        m=strlen(P) ;
        KMP() ;
    }
    return 0;
}