Cod sursa(job #3142945)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 26 iulie 2023 11:18:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int dim = 2e6 + 5;
const int MOD = 1e9 + 7;
const int BASE = 257;

char a[dim] , b[dim];
int ph[dim] , pow_base[dim] , n , m , hashS;
vector <int> M;

long long Power(int b , int e)
{
    if(e == 0)
        return 1LL;
    else if(e % 2)
        return (1LL * (b % MOD) * (Power(b , e - 1) % MOD)) % MOD;
    else
    {
        long long p = Power(b , e / 2) % MOD;
        return (1LL  * p * p) % MOD;
    }
}

int InvMod (int n)
{
    return Power(n , MOD - 2);
}

inline int Min (int a , int b)
{
    if(M.size() > 1000)
        return 1000;
    else
        return M.size();
}

int HashSecv (int p)
{
    long long x =  (ph[p] - ph[max(0 , p - n)]) % MOD;
    while(x < 0) x += MOD;
    return (1LL * x % MOD * (InvMod(pow_base[p - n+1]) % MOD)) % MOD;
}

int main()
{
    fin >> a >> b;
    n = strlen(a);
    m = strlen(b);
    pow_base[0] = 1;
    for(int i = 1 ; i < m ; ++i)
        pow_base[i] = (1LL * (pow_base[i - 1] % MOD) * (BASE % MOD)) % MOD;
    /// Hash-ul stringului in care voi cauta
    ph[0] = pow_base[0] * (b[0] - 'A' + 1);
    for(int i = 1 ; i < m ; ++i)
        ph[i] = (ph[i - 1] % MOD + 1LL * (pow_base[i] * (b[i] - 'A' + 1)) % MOD) % MOD;
    /// Hash-ul stringului pe care il caut
    for(int i = 0 ; i < n ; ++i)
        hashS = (hashS + (pow_base[i] * (a[i] - 'A' + 1)) % MOD) % MOD;
    for(int i = n - 1 ; i < m ; ++i)
    {
        if(HashSecv(i) == hashS)
            {
                if(M.size() < 1000)
                    M.push_back(i - n + 1);
                else
                    break;
            }
    }
    if(M.size() > 1000)
        fout << "1000\n";
    else
        fout << M.size() << '\n';
    for(int i = 0 ; i < Min(M.size() , 1000) ; ++i)
        fout << M[i] << " ";
}