Cod sursa(job #3153674)

Utilizator ungureanubogdan07Ungureanu Bogdan ungureanubogdan07 Data 30 septembrie 2023 16:32:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string a, b;
long long hash1, hash2, p1, p2, aux1 = 1, aux2 = 1;
int MOD1 = 666013, MOD2 = 10027, baza = 73;
vector<int> rez;

int main()
{
    cin >> a >> b;
    for(int i = 0; i < a.size(); ++i) {
        hash1 = (hash1 * baza + a[i]) % MOD1;
        hash2 = (hash2 * baza + a[i]) % MOD2;
        if(i) aux1 = (aux1 * baza) % MOD1, aux2 = (aux2 * baza) % MOD2;
    }
    for(int i = 0; i < a.size(); ++i) {
        p1 = (p1 * baza + b[i]) % MOD1;
        p2 = (p2 * baza + b[i]) % MOD2;
    }
    if(p1 == hash1 && p2 == hash2) rez.push_back(0);
    for(int i = a.size(); i < b.size(); ++i) {
        p1 = ((((p1 - aux1 * b[i - a.size()]) % MOD1) + MOD1) * baza + b[i]) % MOD1;
        p2 = ((((p2 - aux2 * b[i - a.size()]) % MOD2) + MOD2) * baza + b[i]) % MOD2;
        if(p1 == hash1 && p2 == hash2) rez.push_back(i - a.size() + 1);
    }
    cout << rez.size() << '\n';
    for(int i = 0; i < min(1000, (int) rez.size()); ++i) cout << rez[i] << ' ';
    return 0;
}