Cod sursa(job #3279844)

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

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

const unsigned long long base = 257;
const unsigned long long mod = 1000000009ULL;

unsigned long long calculateHash(const string& s) {
    unsigned long long h = 0;
    for (char c : s) {
        h = (h * base + (unsigned char)c) % mod;
    }
    return h;
}

unsigned long long updateHash(unsigned long long oldHash, char removed, char added, unsigned long long basePower) {
    oldHash = (oldHash + mod - (unsigned long long)(unsigned char)removed * basePower % mod) % mod;
    oldHash = (oldHash * base + (unsigned char)added) % mod;
    return oldHash;
}

bool checkSubstring(const string& B, int start, const string& A) {
    if (start + (int)A.size() > (int)B.size()) return false;
    return (B.compare(start, A.size(), A) == 0);
}

vector<int> findSubstrings(const string& A, const string& B) {
    int n = (int)A.size(), m = (int)B.size();
    vector<int> r;
    if (n > m) return r;
    unsigned long long hashA = calculateHash(A);
    unsigned long long hashB = calculateHash(B.substr(0, n));
    unsigned long long basePower = 1;
    for (int i = 0; i < n - 1; ++i) {
        basePower = (basePower * base) % mod;
    }
    if (hashA == hashB && checkSubstring(B, 0, A)) {
        r.push_back(0);
    }
    for (int i = 1; i <= m - n; ++i) {
        hashB = updateHash(hashB, B[i - 1], B[i + n - 1], basePower);
        if (hashA == hashB && checkSubstring(B, i, A)) {
            r.push_back(i);
        }
    }
    return r;
}

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