Cod sursa(job #1969689)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 18 aprilie 2017 16:32:20
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdint.h>
#include <fstream>
#include <string.h>
#define nmax 10000001
#define mmax 21
using namespace std;
fstream f1("abc2.in", ios::in);
fstream f2("abc2.out", ios::out);
char sir[nmax], cuv[mmax];
const int16_t q=131, d=3;
int16_t m, t[nmax], viz[nmax], pa;
int32_t n, rez;
int16_t maxim()
{
    int16_t i, s=1;
    for(i=1; i<m; i++)
        {
            s*=3;
            s%=q;
        }
     return s;
}
int main()
{
    f1.getline(sir, nmax);
    f1.getline(cuv, mmax);
    n=strlen(sir);
    m=strlen(cuv);
    int32_t i, maxi;
    int16_t j, val;
    maxi=maxim();///3^(m-1)%q
    ///construiesti prima secv din textul mare
    for(i=0; i<m; i++)
        {
            if(sir[i]=='a') val=1;
            else if(sir[i]=='b') val=2;
                 else val=3;
            t[0]=t[0]*3+val;
            t[0]%=q;
        }
    ///retii si celelalte secvente
    for(i=1; i<=n-m; i++)
    {
        if(sir[i-1]=='a') val=1;
            else if(sir[i-1]=='b') val=2;
                 else val=3;
        t[i]=(t[i-1]-maxi*val+d*q)%q;
        if(sir[i+m-1]=='a') val=1;
            else if(sir[i+m-1]=='b') val=2;
                 else val=3;
        t[i]=(t[i]*d+val)%q;
    }

    ///pentru toate cuv din dex
    do
    {
        ///creezi patternul curent
        pa=0;
        for(j=0; j<m; j++)
        {
            if(cuv[j]=='a') val=1;
            else if(cuv[j]=='b') val=2;
                 else val=3;

            pa=pa*3+val;
            pa%=q;
        }
        ///il cauti in textul mare si il marchezi daca il gasesti
        for(i=0; i<n-m; i++)
            if(t[i]==pa)
        {
            ///cauta
            int16_t ok=1;
            for(j=0; j<m; j++)
                if(sir[i+j]!=cuv[j]) {ok=0; break;}
            if((ok)&&(!viz[i]))
            {
                viz[i]=1;
                rez++;
            }
        }

    }
    while(f1>>cuv);

    f2<<rez;
    return 0;
}