Cod sursa(job #2974894)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 4 februarie 2023 19:47:55
Problema Aho-Corasick Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

const int NMAX=1e4+5;

int p[NMAX];

string s;
string a;

void kmp(int n)
{
    int i,k=0;
    for(i=1;i<n;i++)
    {
        while(a[i]!=a[k] && k>0)
            k=p[k-1];
        if(a[i]==a[k])
            k++;
        p[i]=k;
    }
}

int main()
{
    int n,m,saiz,i,j;
    fin>>s>>n;
    m=s.size();
    for(i=1;i<=n;i++)
    {
        int k=0,kon=0;
        fin>>a;
        saiz=a.size();
        for(j=0;j<=saiz;j++)
            p[j]=0;
        kmp(saiz);
        for(j=0;j<m;j++)
        {
            while(s[j]!=a[k] && k>0)
                k=p[k-1];
            if(s[j]==a[k])
                k++;
            if(k==saiz)
                kon++;
        }
        fout<<kon<<"\n";
    }
    return 0;
}