Cod sursa(job #3356940)

Utilizator pascarualexPascaru Alexandru pascarualex Data 4 iunie 2026 20:37:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include<fstream>
#include<iostream>
#include<vector>

#define mod1 100019
#define mod2 100043
#define p 256

using namespace std;

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

vector<int> sol;

int main() {

    string s, t;
    fin >> s >> t;

    int n = s.size(), m = t.size();

    int hash1 = 0, hash2 = 0;
    int h1 = 0, h2 = 0;
    int p1 = 1, p2 = 1;

    if (m < n) {
        fout << "0" << '\n';
        return 0;
    }

    for (int i = 0; i < n; i ++) {
        hash1 = (hash1 * p + s[i]) % mod1;
        hash2 = (hash2 * p + s[i]) % mod2;

        h1 = (h1 * p + t[i]) % mod1;
        h2 = (h2 * p + t[i]) % mod2;

        if (i != 0) {
            p1 = p1 * p % mod1;
            p2 = p2 * p % mod2;
        }
    }

    if (h1 == hash1 && h2 == hash2) {
        sol.push_back(0);
    }

    for (int i = n; i < m; i ++) {
        h1 = ((h1 - (t[i-n] * p1) % mod1 + mod1) * p  + t[i])% mod1;
        h2 = ((h2 - (t[i-n] * p2) % mod2 + mod2) * p  + t[i])% mod2;

        if (h1 == hash1 && h2 == hash2) {
            sol.push_back(i - n + 1);
        }
    }

    fout << sol.size() << '\n';
    for (int i = 0; i < min((int)sol.size(), 1000); i++) {
        fout << sol[i] << ' ';
    }



}