Cod sursa(job #3138814)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 22 iunie 2023 14:40:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>

const int P = 67;
const int M = 1e9 + 9;

long long get_code(char x) {
    if ('0' <= x && x <= '9') return x - '0' + 53;
    else if ('a' <= x && x <= 'z') return x - 'a' + 1;
    else return x - 'A' + 27;
}

int main() {
    std::ifstream input("strmatch.in");
    std::ofstream output("strmatch.out");

    std::string s, t;
    input >> s >> t;

    std::vector<long long> pow(std::max(s.size(), t.size()));
    pow[0] = 1;
    for (int i = 1; i < pow.size(); ++i) {
        pow[i] = pow[i - 1] * P % M;
    }
    std::vector<long long> hash_sum(t.size() + 1, 0);

    int size = (int) t.size();

    for (int i = 0; i < size; ++i) {
        hash_sum[i + 1] = (hash_sum[i] + get_code(t[i]) * pow[i]) % M;
    }

    long long search_hash = 0;
    for (int i = 0; i < s.size(); ++i) {
        search_hash = (search_hash + get_code(s[i]) * pow[i]) % M;
    }

    std::vector<int> pos;

    for (int i = 0; i - 1 + s.size() < size; ++i) {
        long long current_hash = (hash_sum[i + s.size()] + M - hash_sum[i]) % M;
        if (search_hash * pow[i] % M == current_hash) pos.push_back(i);
    }
    output << pos.size() << '\n';
    for (const auto &x: pos) output << x << " ";

    return 0;
}