Mai intai trebuie sa te autentifici.

Cod sursa(job #2301372)

Utilizator ahriAhriixd ahri Data 12 decembrie 2018 21:12:52
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include<stdio.h>

#include<string.h>

using namespace std;



#define FIN "ahocorasick.in"

#define FOUT "ahocorasick.out"

#define WORDLEN 100000

#define STRINGLEN 1000000

#define ascii (int)'a'

char str[STRINGLEN];

char word[WORDLEN];

int n;

int strlength;







int compare(char word[],int index, int length)

{

    for(int i=0;i<length;i++)

    {

        if(word[i] != str[index + i])

            return 1;

    }



    return 0;

}





int countStr(char word[])

{

    int table[26]; //bad mismatch table

    int length = strlen(word);



    //preprocessing

    for(int i=0; i < 26; i++)

    {

        table[i] = length;

    }



    for(int i=0;i<length;i++)

    {

        table[(int)word[i] - ascii] = length - i - 1;



        if(table[(int)word[i] - ascii] == 0)

            table[(int)word[i] - ascii] = 1;

    }









    //comparison

    int index = 0;

    int counter = 0;

    while(index + length <= strlength)

    {



        if(compare(word,index, length) == 0)

        {

            counter++;

            index++;

        }

        else

        {

            index += table[str[index+length] - ascii];

        }

    }

    return counter;

}





int main()

{

    freopen(FIN, "r", stdin);

    freopen(FOUT, "w", stdout);



    gets(str);

    scanf("%d ", &n);

    strlength = strlen(str);

    for(int i=1;i<=n;i++)

    {

        gets(word);

        printf("%d \n",countStr(word));

    }







    return 0;

}