Cod sursa(job #2832396)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 13 ianuarie 2022 16:24:00
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

typedef unsigned int uint;
const int mod=50021;

char l[10000010],ch[30];
unsigned int v[90907];
vector <uint> h[mod];

bool fct(uint x, bool ok){
    uint aux;

    aux=x%mod;

    for (vector <uint>::iterator it=h[aux].begin(); it!=h[aux].end(); ++it){
        if (*it==x){
            return 1;
        }
    }

    if (ok){
        h[aux].push_back(x);
    }
    return 0;
}

int main()
{
    unsigned int m,n,i,j,aux,sol=0,x=0;
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    l[0]='a';
    fgets(l+1,10000005,stdin);
    n=strlen(l)-2;
    fgets(ch,25,stdin);
    m=strlen(ch)-1;
    for (i=0;i<m;++i)
        v[1]=v[1]*3+ch[i]-'a';
    fct(v[1], 1);
    i=1;
    while (!feof(stdin))
    {
        ++i;
        fgets(ch,25,stdin);
        for (j=0;j<m;++j)
            v[i]=v[i]*3+ch[j]-'a';
        fct(v[i], 1);
        //fprintf(stderr, "%u ", v[i]);
    }

    for (aux=1,i=1;i<m;++i)
    {
        aux*=3;
        x=x*3+l[i]-'a';
    }
    //fprintf(stderr, "\n\n%u %u\n\n", aux, x);
    for (j=1;j<=n-m+1;++j)
    {
        x=(x-(l[j-1]-'a')*aux)*3+l[j+m-1]-'a';
        if (fct(x, 0))
            ++sol;
        //fprintf(stderr, "%u, %u: %u\n", j, x, sol);
    }
    printf("%u\n",sol);
    return 0;
}