Cod sursa(job #2494751)

Utilizator KernelovicNegrean Victor Kernelovic Data 18 noiembrie 2019 13:00:03
Problema Aho-Corasick Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define DL 1000005
#define DC 10005

using namespace std;

char txt[DL], c[DC];
int n, pi[DC], lg, lgc;

void kmp()
{
    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()
{
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    cin >> txt + 1 >> n;
    lg = strlen(txt + 1);

    for(int k = 1; k <= n; k++)
    {
        cin >> c + 1;
        lgc = strlen(c + 1);
        int pot = 0;

        for(int i = 0; i <= lgc; i++) pi[i] = 0;

        kmp();

        for(int i = 1, q = 0; i <= lg; i++)
        {
            for(; q != 0 && txt[i] != c[q + 1]; q = pi[q]);

            if(txt[i] == c[q + 1]) q++;

            if(q == lgc) pot++;
        }
        cout << pot << endl;
    }
    return 0;
}