Cod sursa(job #3279849)

Utilizator schema_227Stefan Nicola schema_227 Data 24 februarie 2025 16:13:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

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

static const unsigned long long base1 = 31ULL;
static const unsigned long long mod1  = 1000000009ULL;
static const unsigned long long base2 = 53ULL;
static const unsigned long long mod2  = 1000000007ULL;

struct TwoHash {
    unsigned long long h1, h2;
};

TwoHash calcHash(const string &s) {
    TwoHash H{0ULL, 0ULL};
    for (char c : s) {
        unsigned char uc = (unsigned char)c;
        H.h1 = (H.h1 * base1 + uc) % mod1;
        H.h2 = (H.h2 * base2 + uc) % mod2;
    }
    return H;
}

TwoHash updateHash(const TwoHash &oldH, char removed, char added, unsigned long long p1, unsigned long long p2) {
    TwoHash nH = oldH;
    unsigned long long r = (unsigned char)removed;
    unsigned long long a = (unsigned char)added;
    nH.h1 = (nH.h1 + mod1 - (r * p1) % mod1) % mod1;
    nH.h1 = (nH.h1 * base1 + a) % mod1;
    nH.h2 = (nH.h2 + mod2 - (r * p2) % mod2) % mod2;
    nH.h2 = (nH.h2 * base2 + a) % mod2;
    return nH;
}

vector<int> findSubstrings(const string &A, const string &B) {
    int n = (int)A.size();
    int m = (int)B.size();
    vector<int> r;
    if (n > m) return r;
    TwoHash hA = calcHash(A);
    TwoHash hB = calcHash(B.substr(0, n));
    unsigned long long p1 = 1ULL, p2 = 1ULL;
    for (int i = 0; i < n - 1; i++) {
        p1 = (p1 * base1) % mod1;
        p2 = (p2 * base2) % mod2;
    }
    if (hA.h1 == hB.h1 && hA.h2 == hB.h2) {
        r.push_back(0);
    }
    for (int i = 1; i <= m - n; i++) {
        hB = updateHash(hB, B[i - 1], B[i + n - 1], p1, p2);
        if (hB.h1 == hA.h1 && hB.h2 == hA.h2) {
            r.push_back(i);
        }
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    string A, B;
    in >> A >> B;
    vector<int> ans = findSubstrings(A, B);
    out << (int)ans.size() << "\n";
    int limit = ans.size();
    if (limit > 1000) limit = 1000;
    for (int i = 0; i < limit; i++) {
        out << ans[i] << " ";
    }
    out << "\n";
    return 0;
}