Cod sursa(job #2903520)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 17 mai 2022 17:26:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
#define MOD 1000003
#define MOD2 1000007
#define baza 123
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int h1, h2, H1, H2;
char sir1[2000001];
char sir2[2000001];
vector <int> rasp;
long long int poww(int a, int x);
long long int poww2(int a, int x);

int main()
{
    int x, y, i;
    fin.getline(sir1, 2000002);
    fin.getline(sir2, 2000002);
    h1=0;
    H1=0;
    x=strlen(sir1);
    for(i=0; i<x; i++)
    {
        h1=(h1*baza+sir1[i])%MOD;
        H1=(H1*baza+sir1[i])%MOD2;
    }
    h2=0;
    H2=0;
    y=strlen(sir2);
    for(i=0; i<x; i++)
    {
        h2=(h2*baza+sir2[i])%MOD;
        H2=(H2*baza+sir2[i])%MOD2;
    }
    if(h1==h2 && H1==H2)
    {
        rasp.push_back(0);
    }
    for(i=x; i<y && rasp.size() < 1000; i++)
    {
        h2=((h2-(sir2[i-x]*poww(baza, x-1))%MOD+MOD)*baza+sir2[i])%MOD;
        H2=((H2-(sir2[i-x]*poww2(baza, x-1))%MOD2+MOD2)*baza+sir2[i])%MOD2;

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

    if(x > y) fout << 0 << '\n';
    else
    {
        fout<<rasp.size()<<'\n';
        for(int i:rasp) fout<<i<<' ';
    }

    return 0;
}
long long int poww(int a, int x)
{
    if(x==0)
        return 1;
    long long int y=poww(a, x/2);
    if(x%2==0)
        return (y*y)%MOD;
    else
        return (y*y*a)%MOD;
}
long long int poww2(int a, int x)
{
    if(x==0)
        return 1;
    long long int y=poww(a, x/2);
    if(x%2==0)
        return (y*y)%MOD2;
    else
        return (y*y*a)%MOD2;
}