Cod sursa(job #1394066)

Utilizator retrogradLucian Bicsi retrograd Data 19 martie 2015 23:18:13
Problema Aho-Corasick Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 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;
    }
}

var BAD[256];

void build_bad() {
    var l = strlen(S);
    fill(BAD, BAD+256, l);
    for(var i=0; i<l-1; i++) {
        BAD[S[i]-'a'] = l - i - 1;
    }
}

int main() {

    var n;

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

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

        build_bad();

        for(var i=size; STR[i];) {
            var j = size;
            var k = i;
            while(j>=0 && STR[k] ==S[j]) {
                j --;
                k --;
            }
            if(j < 0) {
                count ++;
                i++;
            } else {
                i = k + BAD[STR[k]-'a'];
            }
        }

        fout<<count<<'\n';

    }

    return 0;
}