Cod sursa(job #2494851)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 18 noiembrie 2019 16:53:05
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstring>
#include <iostream>
#include <fstream>
#include <set>
#define NMAX 1000
using namespace std;

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

char T[10000009], P[50009];
int n,m;

set<int> S;

unsigned long putere(int d, int m)
{
    int i;
    unsigned long p=1;
    for(i=1; i<m; ++i)
        p*=d;
    return p;
}

int EQ(char *P, char *T, int k)
{
    int i;
    for(i=0; i<m; ++i)
        if(P[i]!=T[k+i])
            return 0;
    return 1;
}


void RabinKarp( char *T, char *P, int d, int q)
{
    unsigned long h, p, t0;
    int ct=0;
    n = strlen(T);
    m = strlen(P);
    h = putere(d,m)%q;
    p = t0 = 0;
    for(int i=0; i<m; ++i) //calculez p si t0 initial
    {
        p = (d*p + P[i])%q;
        t0 = (d*t0 + T[i])%q;
    }
    for(int k=0; k<=n-m; ++k) //incerc toate posibilele deplasamente
    {
        if(p==t0)
            if( EQ(P,T,k)) // am gasit la pozitia k
                S.insert(k);
        t0 = (t0 + d*q - T[k]*h)%q; //recalculez t0
        t0 = (t0*d + T[k+m])%q;
    }
}

int main()
{
    int poz;
    fin>>T;
    int ct=0;
    while(fin>>P)
    {
        RabinKarp(T,P,128,131);
    }
    fout<<S.size();
    return 0;
}