Cod sursa(job #1385934)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 12 martie 2015 16:09:53
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream is("ahocorasick.in");
ofstream os("ahocorasick.out");

char A[1000002];
char B[10002];
int PI[1000002];
int N, k, lenB, lenA, Sol;

void BuildPI()
{
    k = 0;
    for ( int i = 2; i <= lenB; ++i )
    {
        while ( k > 0 && B[k+1] != B[i] )
            k = PI[k];

        if ( B[k+1] == B[i] )
            k++;

        PI[i] = k;
    }
}

void CountApp()
{
    k = 0;
    for ( int i = 1; i <= lenA; ++i )
    {
        while ( k > 0 && B[k+1] != A[i] )
            k = PI[k];

        if ( B[k+1] == A[i] )
            k++;

        if ( k == lenB )
            Sol++;
    }
}


int main()
{
    is >> A+1;
    lenA = strlen(A+1);
    is >> N;
    for ( int i = 1; i <= N; ++i )
    {
        Sol = 0;
        is >> B+1;
        lenB = strlen(B+1);
        for ( int j = 1; j <= lenB; ++j )
            PI[j] = 0;

        BuildPI();
        CountApp();

        os << Sol << '\n';

    }
}