Cod sursa(job #3277808)

Utilizator schema_227Stefan Nicola schema_227 Data 17 februarie 2025 13:53:13
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 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 = 31;
const unsigned long long mod = 1e9 + 9;

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

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

vector<int> findSubstrings(const string& A, const string& B) {
    int n = A.size(), m = B.size();
    vector<int> result;

    if (n > m) return result;

    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) {
        result.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) {
            result.push_back(i);
        }
    }

    return result;
}

int main() {
    string A, B;
    in >> A >> B;

    vector<int> appearances = findSubstrings(A, B);

    if (!appearances.empty()) {
        out << appearances.size() << '\n';
        for (int pos : appearances) {
            out << pos << " ";
        }
        out << '\n';
    }

    return 0;
}