Cod sursa(job #3359594)

Utilizator radu_flradu fl radu_fl Data 30 iunie 2026 16:56:39
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax=2000005;
const int base=73;
const int mod1=1000000007;
const int mod2=1000000009;
int coda1[nmax],codb1[nmax],p1[nmax];
int coda2[nmax],codb2[nmax],p2[nmax];
int sol[nmax];
void encode(string s,int cod[],int mod){
    int n=s.size();
    cod[0]=(int)s[0];
    for(int i=1;i<n;i++)
        cod[i]=(1LL*base*cod[i-1]+(int)s[i])%mod;
}
int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string a,b;
    fin>>a>>b;
    int n=a.size(),m=b.size();
    encode(a, coda1, mod1);
    encode(b, codb1, mod1);
    encode(a, coda2, mod2);
    encode(b, codb2, mod2);
    p1[0]=p2[0]=1;
    for(int i=1;i<=m;i++){
        p1[i]=1LL*p1[i-1]*base%mod1;
        p2[i]=1LL*p2[i-1]*base%mod2;
    }
    int hasha1=coda1[n-1],hasha2=coda2[n-1],cnt=0;
    for(int st=0;st+n-1<m;st++){
        int dr=st+n-1;
        int hash1,hash2;
        if(st==0){
            hash1=codb1[dr];
            hash2=codb2[dr];
        }
        else{
            hash1=(codb1[dr]-1LL*codb1[st-1]*p1[n]%mod1+mod1)%mod1;
            hash2=(codb2[dr]-1LL*codb2[st-1]*p2[n]%mod2+mod2)%mod2;
        }
        if(hash1==hasha1 && hash2==hasha2){
            sol[cnt]=st;
            cnt++;
        }
    }
    fout<<cnt<<'\n';
    for(int i=0;i<cnt && i<1000;i++)
        fout<<sol[i]<<' ';
    return 0;
}