Cod sursa(job #3250299)

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