Cod sursa(job #2232357)

Utilizator MaaaaaCristina Ma Maaaaa Data 18 august 2018 19:55:32
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <string.h>
#define ll long long
#define mod1 100003
#define mod2 666013
#define p 73 //poti avea si litere mari
using namespace std;
fstream f1("strmatch.in", ios::in);
fstream f2("strmatch.out", ios::out);
char sir[2000005], pat[2000005];
int n, m, nrpos, pos[2000005];//n=lung sir, m=lung pat
ll h1pat, h2pat, p1max=1, p2max=1, h1, h2;
//h1pat=( pat[0]*p^(m-1)+ pat[1]*p^(m-2)+ ...+pat[m-1]*p^0)%mod1
//h2pat=( pat[0]*p^(m-1)+ pat[1]*p^(m-2)+ ...+pat[m-1]*p^0)%mod1
//p1max= p^(m-1)%mod1
//p2max= p^(m-1)%mod2
void citire()
{
    f1>>pat>>sir;
    m=strlen(pat); n=strlen(sir);
    for(int i=0; i<m; i++)
    {
        h1pat=(h1pat*p+pat[i])%mod1;
        h2pat=(h2pat*p+pat[i])%mod2;
        if(i>0)
        {
        p1max*=p; p1max%=mod1;
        p2max*=p; p2max%=mod2;
        }
    }
    if(n<m) {f2<<0; return;}
    for(int i=0; i<m; i++)
    {
        h1=(h1*p+sir[i])%mod1;
        h2=(h2*p+sir[i])%mod2;
    }
    if((h1==h1pat)&&(h2==h2pat))
    {
        nrpos++; pos[nrpos]=1;
    }
    for(int i=m; i<n; i++)
    {
        h1=(((h1-sir[i-m]*p1max)%mod1 +mod1) *p + sir[i])%mod1;
        h2=(((h2-sir[i-m]*p2max)%mod2 +mod2)*p + sir[i])%mod2;
        if((h1==h1pat)&&(h2==h2pat))
        {
            nrpos++; pos[nrpos]=i-m+1;
        }
    }
}
void afis()
{
    f2<<nrpos<<"\n";
    for(int i=1; (i<=nrpos)&&(pos[i]<=1000); i++)
        f2<<pos[i]<<' ';
}
int main()
{
    citire();
    afis();
    return 0;
}