Cod sursa(job #1959140)

Utilizator RaduhhNuhay Bebru Raduhh Data 9 aprilie 2017 07:55:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

#define baza 73
#define mod1 100007
#define mod2 100021

using namespace std;

string a,b;
int hasha1,hasha2,hashb1,hashb2,hb1=1,hb2=1,i,nr;
vector <int> v;

int main() 
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>a>>b;
    int n=a.length(),m=b.length();
    for (i=0; i<n; i++)
    {
        hasha1=(hasha1*baza+a[i]) % mod1;
        hasha2=(hasha2*baza+a[i]) % mod2;
        
        hashb1=(hashb1*baza+b[i]) % mod1;
        hashb2=(hashb2*baza+b[i]) % mod2;
        
        if (!i) continue;
        
        hb1=(hb1*baza) % mod1;
        hb2=(hb2*baza) % mod2;
    }
    
    for (i=0; i<=m-n; i++)
    {
        if (hasha1==hashb1 && hasha2==hashb2) nr++,v.push_back(i);
        hashb1=((hashb1-(b[i]*hb1) % mod1 + mod1) * baza + b[i+n]) % mod1;
        hashb2=((hashb2-(b[i]*hb2) % mod2 + mod2) * baza + b[i+n]) % mod2;
    }
    cout<<min(1000,nr)<<'\n';
    for (i=0; i<min(1000,nr); i++)
        cout<<v[i]<<" ";
}