Cod sursa(job #1812340)

Utilizator rangalIstrate Sebastian rangal Data 21 noiembrie 2016 23:19:47
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <cstring>
#define lgmax 2000003
#define in "strmatch.in"
#define out "strmatch.out"
#define base 62 //26 (a-z) 26 (A-Z) 10 (0-9)
#define mod 20047297

typedef unsigned long long ull;

using namespace std;

ifstream fin(in);
ofstream fout(out);

ull Mx;
char A[lgmax],B[lgmax];
int ct=0,rez[1003];

ull HashPw(int bz,ull m)
{
    ull P=1;
    while(--m) // for(int i=1; i<=m-1; ++i)
        P=(P*bz) %mod;
    return P;
}

ull Hash(char *t,int m)
{
    ull H=t[0];
    for(int i=1; i<m; ++i)
        H=(H*base +t[i]) %mod;
    return H;
}

inline bool strcmpf(char *v,char *w,int m)
{
    for(int i=0; v[i]; ++i)
        if(v[i]!=w[i]) return false;
    return true;
}

inline void HashSrch(char *v,const ull ha ,char *w,ull &hb,int poz,int m)
{

    /*for(int i=0; w[i]; ++i) fout<<w[i];
    fout<<"\n";*/


    if(ha==hb && strcmpf(v,w,m))
    {
        ++ct;
        if(ct<=1000) rez[ct]=poz;
    }
    //se elimina valoarea caracterului cel mai semnificativ
    hb=((hb - Mx*w[0] ) %mod ) * base % mod;
    hb=(hb+w[m]) %mod;
    if(hb<0) hb+=mod;
}

int main()
{
    fin>>A>>B;
    int m=strlen(A);
    int n=strlen(B);
    // prima data se stabileste constanta base ^ (m-1) % mod care va elimina caracterul
    // cel mai semnificativ in timp constant
    Mx=HashPw(base,m);

    // determinam valoarea in baza 10 % mod a primelor m caractere din sirurile A si B

    const ull ha=Hash(A,m);
    ull hb=Hash(B,m);

    //fout<<"ha= "<<ha<<"\n";

    // pentru sirul B trebuie sa continuam subsecventa in functie de valoarea ei in
    // baza 10 %mod , si pentru a nu calcula din nou tot, se elimina caracterul cel mai
    // semnificativ si se adauga la capat cel mai nesemnificativ

    for(int i=0; i<=n-m; ++i) // ultimul subsir va fi n-m+1, n-m+2,.... n-m+m ->din m caratctere.
    {
        //fout<<hb<<"\n";
        HashSrch(A,ha,B+i,hb,i,m);
    }

    fout<<ct<<"\n";
    for(int i=1; i<=ct; ++i)
        fout<<rez[i]<<" ";

    fin.close(); fout.close();
    return 0;
}