Cod sursa(job #1323269)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 20 ianuarie 2015 21:10:11
Problema Aho-Corasick Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<stdio.h>
#include<string.h>
using namespace std;

#define FIN "ahocorasick.in"
#define FOUT "ahocorasick.out"
#define WORDLEN 100005
#define STRINGLEN 1000005
#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;
}