Cod sursa(job #1394023)

Utilizator retrogradLucian Bicsi retrograd Data 19 martie 2015 22:34:30
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<cstring>

using namespace std;
typedef int var;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

char STR[1000005];
char S[100005];
var PI[100005];

void build_pi() {
    PI[0] = -1;
    for(var i=1; S[i]; i++) {
        var j = PI[i-1];
        while(j != -1 && S[i] != S[j+1])
            j = PI[j];
        PI[i] = j+1;
    }
}

int main() {

    var n;

    STR[0] = '#';
    fin>>STR+1;
    fin>>n;
    while(n--) {
        S[0] = '#';
        fin>>S+1;
        var size = strlen(S) - 1;

        var j = 0;
        var count = 0;
        build_pi();

        for(var i=1; STR[i]; i++) {
            while(j != -1 && STR[i] != S[j+1])
                j = PI[j];
            j ++;
            if(j == size) {
                count ++;
            }
        }

        fout<<count<<'\n';

    }

    return 0;
}