Cod sursa(job #3153649)

Utilizator DariusM17Murgoci Darius DariusM17 Data 30 septembrie 2023 16:07:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
#define ll long long
const int MOD1=666013,MOD2=65293,baza=75 ;
string a,b ;
ll hashA1,hashA2,aux1=1,aux2=1,h1,h2 ;
vector <int> ans ;
int main()
{
    fin>>a>>b ;
    for(int i=0; i<a.size(); ++i)
    {
        hashA1=(hashA1*baza+a[i])%MOD1 ;
        hashA2=(hashA2*baza+a[i])%MOD2 ;
        if(i!=0) aux1=(aux1*baza)%MOD1,aux2=(aux2*baza)%MOD2 ;
    }
    for(int i=0; i<a.size(); ++i)
    {
        h1=(h2*baza+b[i])%MOD1 ;
        h2=(h2*baza+b[i])%MOD2 ;
    }
    if(hashA1==h1 && hashA2==h2) ans.push_back(0) ;
    for(int i=a.size(); i<b.size(); ++i)
    {
        h1=((((h1-b[i-a.size()]*aux1)%MOD1+MOD1)%MOD1)*baza+b[i])%MOD1 ;
        h2=((((h2-b[i-a.size()]*aux2)%MOD2+MOD2)%MOD2)*baza+b[i])%MOD2 ;
        if(hashA1==h1 && hashA2==h2) ans.push_back(i-a.size()+1) ;
    }
    fout<<ans.size()<<'\n' ;
    for(int i=0; i<min(1000,(int)ans.size()); ++i) fout<<ans[i]<<" ";
    return 0;
}