Cod sursa(job #3277322)

Utilizator vladm98Munteanu Vlad vladm98 Data 15 februarie 2025 18:34:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
#define type int
using namespace std;

const type MOD = 1e9 + 7;
const type SIZE = 2000000;
type powers[SIZE + 1];
type hashes[SIZE + 1];
type base = 512;

void buildRollingHash(string text)
{
    type n = text.size();
    for(type i = n - 1; i >= 0; i--)
    {
        hashes[i] = ((1LL * hashes[i + 1] * base) % MOD + text[i]) % MOD;
    }
}

void buildPowerVector(string text)
{
    type n = text.size();
    powers[0] = 1;
    for(type i = 1; i <= n; i++)
    {
        powers[i] = (1LL * powers[i - 1] * base) % MOD;
    }
}

type buildHash(string text)
{
    type n = text.size();
    type hash = 0;
    for(type i = n - 1; i >= 0; i--)
    {
        hash = ((1LL * hash * base) % MOD + text[i]) % MOD;
    }
    return hash;
}

type retriveSequenceHashFromRollingHash(type left, type right)
{
    return ((hashes[left] - (1LL * hashes[right + 1] * powers[right - left + 1]) % MOD) % MOD + MOD) % MOD;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    string tbf, tbs;
    cin >> tbf >> tbs;
    buildRollingHash(tbs);
    buildPowerVector(tbs);
    int hash = buildHash(tbf);
    int cnt = 0;
    for(int i = 0; i + tbf.size() - 1 < tbs.size(); i++)
    {
        if(retriveSequenceHashFromRollingHash(i, i + tbf.size() - 1) == hash)
        {
            cnt++;
        }
    }
    cout << cnt << "\n";
    cnt = 0;
    for(int i = 0; i + tbf.size() - 1 < tbs.size(); i++)
    {
        if(cnt < 1000 && retriveSequenceHashFromRollingHash(i, i + tbf.size() - 1) == hash)
        {
            cout << i << " ";
            cnt++;
        }
    }
}