Cod sursa(job #2886513)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 7 aprilie 2022 20:41:18
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>

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

int const p = 73;
int const MOD1 = 1e9 + 21;
int const MOD2 = 1e9 + 7;

std::vector <int> aparitii;

int main() {
    std::string s1, s2;
    fin >> s1 >> s2;
    int n1 = s1.length(),
        n2 = s2.length();
    int hash1 = 0,
        hash2 = 0;
    int putere1 = 1,
        putere2 = 1;
    for (int i = 0; i < n1; i++) {
        hash1 = ((hash1 * p) + s1[i] - '0') % MOD1;
        hash2 = ((hash2 * p) + s1[i] - '0') % MOD2;
        if (i != 0) {
            putere1 = (putere1 * p) % MOD1;
            putere2 = (putere2 * p) % MOD2;
        }
    }
    int curr1 = 0,
        curr2 = 0;
    for (int i = 0; i < n1; i++) {
        curr1 = ((curr1 * p) + s2[i] - '0') % MOD1;
        curr2 = ((curr2 * p) + s2[i] - '0') % MOD2;
    }
    if (curr1 == hash1 && curr2 == hash2)
        aparitii.push_back(0);
    for (int i = n1; i < n2; i++) {
        curr1 = (curr1 - (s2[i - n1] - '0') * putere1 + MOD1) % MOD1;
        curr2 = (curr2 - (s2[i - n1] - '0') * putere2 + MOD2) % MOD2;
        curr1 = ((curr1 * p) + s2[i] - '0') % MOD1;
        curr2 = ((curr2 * p) + s2[i] - '0') % MOD2;

        if (curr1 == hash1 && curr2 == hash2)
            aparitii.push_back(i - n1 + 1);
    }
    int size = aparitii.size();
    fout << size << "\n";
    size = std::min(size, 1000);
    for (int i = 0; i < size; i++)
        fout << aparitii[i] << " ";
    return 0;
}