Cod sursa(job #2905943)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 24 mai 2022 15:55:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000003
#define MOD2 1000007
#define baza 123

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector < ll > rasp;
ll h1, h2, H1, H2, P1, P2;
char sir1[2000005], sir2[2000005];

int main()
{
    ll x, y, i;

    fin.getline(sir1, 2000005);
    fin.getline(sir2, 2000005);

    h1 = 0, H1 = 0, h2 = 0, H2 = 0, P1 = P2 = 1;
    x = strlen(sir1), y = strlen(sir2);
    if(x > y)
    {
        fout << 0;
        return 0;
    }

    for(i = 0; i < x; i++)
    {
        h1 = (h1 * baza + sir1[i]) % MOD;
        H1 = (H1 * baza + sir1[i]) % MOD2;
    }

    for(i = 0; i < x; i++)
    {
        h2 = (h2 * baza + sir2[i]) % MOD;
        H2 = (H2 * baza + sir2[i]) % MOD2;
        if(i != 0) P1 = (P1 * baza) % MOD, P2 = (P2 * baza) % MOD2;
    }

    if(h1 == h2 && H1 == H2) rasp.push_back(0);
    for(i = x; i < y; i++)
    {
      h2=((h2 - (sir2[i-x] * P1) % MOD + MOD) * baza + sir2[i]) % MOD;
      H2=((H2 - (sir2[i-x] * P2) % MOD2 + MOD2) * baza + sir2[i]) % MOD2;

      if(h1 == h2 && H1 == H2) rasp.push_back(i - x + 1);
    }

    x = rasp.size();
    fout << x << '\n';
    for(i = 0; i < min(999ll, x); i++) fout << rasp[i] << ' ';

    return 0;
}