Cod sursa(job #3142954)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 26 iulie 2023 12:02:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 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 = 313;

char a[dim] , b[dim];
long long ph[dim] , inv[dim] , pow_base[dim] , n , m;
long long 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;
        }
}
long long InvMod (int n)
{
    return Power(n , MOD - 2) % MOD;
}

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[p - n]) % MOD;
    while(x < 0) x += MOD;
    return (1LL * (x % MOD) * (inv[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;
    for(int i = 0 ; i < m ; ++i)
        inv[i] = InvMod(pow_base[i]);
    /// Hash-ul stringului in care voi cauta
    ph[0] = (1LL * pow_base[0] *(int)(b[0])) % MOD;
    for(int i = 1 ; i < m ; ++i)
        ph[i] = ((ph[i - 1] % MOD) + 1LL * (pow_base[i] * (int)(b[i])) % MOD) % MOD;
    /// Hash-ul stringului pe care il caut
    for(int i = 0 ; i < n ; ++i)
        hashS = (hashS % MOD + 1LL * (pow_base[i] % MOD * (int)(a[i])) % 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] << " ";
}