Cod sursa(job #3274485)

Utilizator Robert_NicuNicu Robert Cristian Robert_Nicu Data 6 februarie 2025 21:53:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define int long long
#define DIM 2000001
#define mod 1000000009
#define base 1087

using namespace std;

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

string s;

int n, target, len;

int hash_[DIM], p[DIM];

queue <int> ans;

int i, j;

void precalc_pow(){

    p[1] = base;

    int s0 = s.size();

    for(int i = 2; i <= s0; i++)

        p[i] = (p[i-1] * base) % mod;

}

void precalc_hash(){

    int s0 = s.size();

    for(int j = 1; j <= s0; j++)

        hash_[j] = ((hash_[j-1] * base) % mod + s[j-1]) % mod;

}

int get_hash(int l, int r){

    int ret = hash_[r] - (hash_[l-1] * p[r-l+1]) % mod;

    return (ret + mod) % mod;

}

int32_t main(){

    fin >> s;

    precalc_pow();

    n -= s.size();

    len = s.size();

    precalc_hash();

    target = get_hash(1, len);

    fin >> s;

    precalc_pow();

    n += (s.size() + 1);

    precalc_hash();

    for(i = 1; i <= n; i++)

        if(target == get_hash(i, i + len - 1)){

            ans.push(i-1), j++;

            if(j == 999) break;

        }

    fout << j << "\n";

    while(!ans.empty()){

        fout << ans.front() << " ";

        ans.pop();

    }

}