Cod sursa(job #2574712)

Utilizator serbandonceanSerban Doncean serbandoncean Data 6 martie 2020 09:10:12
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define MODULO1 100019
#define MODULO2 100021
#define DMAX 2000000
#define putere 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int hash1a,hash2a,hash1b,hash2b;
char a[DMAX],b[DMAX];
vector<int> v;
int put1,put2;
int main()
{int lg1,i,lg2;
    fin.getline(a,DMAX);
    fin.getline(b,DMAX);
        lg1=strlen(a);
        lg2=strlen(b);
    put1=put2=1;
    if(lg1>lg2)
    {fout<<0;return 0;}
    for(i=0;i<lg1;i++)
    {
        hash1a=(hash1a*putere+a[i])%MODULO1;
        hash2a=(hash2a*putere+a[i])%MODULO2;
        hash1b=(hash1b*putere+b[i])%MODULO1;
        hash2b=(hash2b*putere+b[i])%MODULO2;
        if(i!=0)
            put1=(put1*putere)%MODULO1,put2=(put2*putere)%MODULO2;
    }
    if(hash1a==hash1b&&hash2a==hash2b)
        v.push_back(0);
    for(i=lg1;i<lg2;i++)
    {
        hash1b=((hash1b-(b[i-lg1]*put1)%MODULO1)*putere+b[i])%MODULO1;
        hash2b=((hash2b-(b[i-lg1]*put2)%MODULO2)*putere+b[i])%MODULO2;
        if(hash1a==hash1b&&hash2a==hash2b)
        v.push_back(i-lg1+1);
    }
    fout<<v.size()<<'\n';
    for(i=0;i<v.size();i++)
        fout<<v[i]<<' ';
    return 0;
}