Cod sursa(job #1323265)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 20 ianuarie 2015 21:03:04
Problema Aho-Corasick Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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;


    //comparison
    int index = 0;
    int counter = 0;
    while(index + length <= strlength)
    {

        if(compare(word,index, length) == 0)
        {
            counter++;
            index++;
        }
        else
        {
            if(table[str[index+length] - ascii] == 0)
                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;
}