Cod sursa(job #1812937)

Utilizator rangalIstrate Sebastian rangal Data 22 noiembrie 2016 16:10:45
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <iostream>
#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 666013
#define mod2 666017

typedef unsigned long long ull;

using namespace std;

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

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

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

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

inline void HashSrch(char *v,const ull ha,const ull ha2 ,char *w,ull &hb,ull &hb2,int poz,int m)
{
    if(ha==hb && ha2==hb2)
    {
        ++ct;
        if(ct<=1000) rez[ct]=poz;
    }

    hb=( (hb - Mx*w[0]%mod +mod) * base +w[m] ) %mod;
    hb2=( (hb2 - Mx2*w[0]%mod2 +mod2) * base +w[m] ) %mod2;
}

int main()
{
    fin>>A>>B;
    int m=strlen(A);
    int n=strlen(B);

    if(m>n)
    {
        fout<<"0\n";
        return 0;
    }

    Mx=HashPw(base,m,mod);
    Mx2=HashPw(base,m,mod2);

    const ull ha=Hash(A,m,mod);
    const ull ha2=Hash(A,m,mod2);
    ull hb=Hash(B,m,mod);
    ull hb2=Hash(B,m,mod2);

    for(int i=0; i<=n-m; ++i)
        HashSrch(A,ha,ha2,B+i,hb,hb2,i,m);

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

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