Cod sursa(job #721717)

Utilizator sana1987Laurentiu Dascalu sana1987 Data 24 martie 2012 00:11:20
Problema Aho-Corasick Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N ('z' - 'a' + 1)

typedef struct trie_node {
    int counter;
    struct trie_node *children[N];
} trie;

trie *new_node() {
    trie *t;
    t = (trie *)malloc(sizeof(trie));
    t->counter = 0;
    memset(t->children, 0, sizeof(t->children));
    return t;
}

void insert(trie *t, char *str) {
    if (*str == '\0')
        return;
    int index = str[0] - 'a';
    if (!t->children[index])
        t->children[index] = new_node();
    t->children[index]->counter++;
    insert(t->children[index], str + 1);
}

int counter(trie *t, char *word) {
    if (*word == '\0')
        return t->counter;
    int index = word[0] - 'a';
    return counter(t->children[index], word + 1);
}

void print(trie *t) {
    printf("%d\n", t->counter);
    int i;
    for (i=0;i<N;i++) {
        if (t->children[i]) {
            printf("%c\n", i + 'a');
            print(t->children[i]);
        }
    }
}

static char line[1000002];
static char word[10002];

int main() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    trie *t = new_node();
    fgets(line, 1000001, stdin);
    int nl = strlen(line), i;
    line[nl - 1] = '\0';
    nl--;
    for (i=0;i<nl;i++) {
        insert(t, line + i);
    }
    int n, k;
    scanf("%d", &n);
    for (k=0;k<n;) {
        word[0] = '\0';
        fgets(word, 10001, stdin);
        int nw = strlen(word);
        if (word[nw - 1] == '\n') {
            word[nw - 1] = '\0';
            nw--;
        }
        if (!nw) continue;
        k++;
        word[nw] = '\0';
        printf("%d\n", counter(t, word));
    }

    return 0;
}