Cod sursa(job #3126163)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 6 mai 2023 11:47:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
long long MOD1=1000000007, MOD2=1000000009, x, y, a, b, p1=1, p2=1, r[2000005], nr, i, n, m;
int main()
{
    fin>>s2>>s1;
    m=s2.size();
    n=s1.size();
    for (i=0; i<m; i++) {
        x=(127*x+(s2[i]-'0'+1))%MOD1;
        y=(127*y+(s2[i]-'0'+1))%MOD2;
        if (i!=0) {p1=(p1*127)%MOD1; p2=(p2*127)%MOD2;}
    }
    for (i=0; i<m; i++) {
        a=(127*a+(s1[i]-'0'+1))%MOD1;
        b=(127*b+(s1[i]-'0'+1))%MOD2;
    }
    if (x==a && y==b) {
        r[++nr]=0;
    }
    for (i=m; i<n; i++) {
        a=(((MOD1+a-((s1[i-m]-'0'+1)*p1)%MOD1)%MOD1)*127+(s1[i]-'0'+1))%MOD1;
        b=(((MOD2+b-((s1[i-m]-'0'+1)*p2)%MOD2)%MOD2)*127+(s1[i]-'0'+1))%MOD2;
        if (x==a && y==b) r[++nr]=i-m+1;
    }
    fout<<nr<<'\n';
    for (i=1; i<=min(nr, 1000ll); i++) {
        fout<<r[i]<<' ';
    }
    return 0;
}