Cod sursa(job #2245843)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 25 septembrie 2018 23:09:10
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
const int DL=1000005;
const int  DC=10005;
char tx[DL],c[DC];
int n,pi[DC],lg,lgc;

void p() {
    for(int i=2,q=0; i<=lgc; ++i) {
        for(;q!=0 && c[i]!=c[q+1];q=pi[q]);
        if(c[i]==c[q+1])
            ++q;
        pi[i]=q;
    }
}

int main()
{

    lg=strlen(tx+1);
    for(int i=1;i<=lg;i++)
        f>>tx[i];
    for(int k=1; k<=n; ++k) {
        f>>c[k];
        lgc=strlen(c+1);
        int pot=0;
        for(int i=0; i<=lgc; ++i) pi[i]=0;
        p();
        for(int i=1,q=0; i<=lg; ++i) {
            for(;q!=0 && tx[i]!=c[q+1]; q=pi[q]);
            if(tx[i]==c[q+1]) ++q;
            if(q==lgc) ++pot;
        }
        g<<pot<<"\n";
    }
    return 0;
}