Cod sursa(job #2553485)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 22 februarie 2020 01:15:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define b1 27
#define b2 29
#define mod1 100007
#define mod2 666013
#define NM 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,m,nr1,nr2,h1,h2,p1,p2,nrap;
bool fr[NM];
string s,t;

void Read();
void RabinKarp();

int main()
{   Read();
    RabinKarp();
    return 0;
}

void Read()
{   f>>s>>t;
    n=s.size();
    m=t.size();
    p1=p2=1;
    for(int i=0; i<n; i++)
    {   nr1=(nr1*b1+s[i])%mod1;
        nr2=(nr2*b2+s[i])%mod2;
        if(i)
        {   p1=(p1*b1)%mod1;
            p2=(p2*b2)%mod2;
        }
    }
}

void RabinKarp()
{   if(n>m)
    {   g<<0;
        return;
    }
    for(int i=0; i<n; i++)
    {   h1=(h1*b1+t[i])%mod1;
        h2=(h2*b2+t[i])%mod2;
    }
    if(nr1==h1 && nr2==h2)
        nrap+=(fr[0]=1);
    for(int i=n; i<m; i++)
    {   h1=((h1-(t[i-n]*p1)%mod1+mod1)*b1+t[i])%mod1;
        h2=((h2-(t[i-n]*p2)%mod2+mod2)*b2+t[i])%mod2;
        if(h1==nr1 && h2==nr2)
            nrap+=(fr[i-n+1]=1);
    }
    g<<nrap<<'\n';
    int nrSol=0;
    for(int i=0; i<NM && nrSol<1000; i++)
        if(fr[i])
        {   nrSol++;
            g<<i<<' ';
        }
}