Cod sursa(job #3250246)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 19 octombrie 2024 19:33:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define H1 1000000007
#define H2 1000000009
#define C 127
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
long long n, m, x1=1, x2=1, a1, a2, b1, b2, k;
long long v[2000005], i;
int main()
{
    fin>>a>>b;
    n=a.size();
    m=b.size();
    a1=a2=a[0]-'0';
    x1=x2=1;
    for (i=1; i<n; i++) {
        x1*=C, x2*=C;
        x1%=H1, x2%=H2;
        a1=(a1*C+a[i]-'0')%H1;
        a2=(a2*C+a[i]-'0')%H2;
    }
    b1=b2=b[0]-'0';
    for (i=1; i<n; i++) {
        b1=(b1*C+b[i]-'0')%H1;
        b2=(b2*C+b[i]-'0')%H2;
    }
    if (a1==b1 && a2==b2) {
        v[++k]=0;
    }
    for (i=n; i<m; i++) {
        cout<<b1<<' '<<(b[i-n]-'0')*x1<<' ';
        b1=(b1-((b[i-n]-'0')*x1))%H1;
        b1=(b1*C+b[i]-'0')%H1;
        b2=(b2-((b[i-n]-'0')*x2))%H2;
        b2=(b2*C+b[i]-'0')%H2;
        if (i==7) cout<<b1<<'\n'<<b2;
        if (b1==a1 && b2==a2) {
            v[++k]=i+1-n;
            if (k>=1000) break;
        }
    }
    fout<<k<<'\n';
    for (i=1; i<=k; i++) {
        fout<<v[i]<<' ';
    }
    return 0;
}