Cod sursa(job #3138816)

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

const int P = 67;
const int M1 = 1e9 + 9;
const int M2 = 1e9 + 7;

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<unsigned int> pow_M1(std::max(s.size(), t.size()));
    std::vector<unsigned int> pow_M2(std::max(s.size(), t.size()));
    pow_M1[0] = 1;
    pow_M2[0] = 1;
    for (int i = 1; i < pow_M1.size(); ++i) {
        pow_M1[i] = pow_M1[i - 1] * P % M1;
        pow_M2[i] = pow_M2[i - 1] * P % M2;
    }
    std::vector<unsigned int> hash_sum_M1(t.size() + 1, 0);
    std::vector<unsigned int> hash_sum_M2(t.size() + 1, 0);

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

    for (int i = 0; i < size; ++i) {
        hash_sum_M1[i + 1] = (hash_sum_M1[i] + get_code(t[i]) * pow_M1[i]) % M1;
        hash_sum_M2[i + 1] = (hash_sum_M2[i] + get_code(t[i]) * pow_M2[i]) % M2;
    }

    long long search_hash_M1 = 0;
    long long search_hash_M2 = 0;
    for (int i = 0; i < s.size(); ++i) {
        search_hash_M1 = (search_hash_M1 + get_code(s[i]) * pow_M1[i]) % M1;
        search_hash_M2 = (search_hash_M2 + get_code(s[i]) * pow_M2[i]) % M2;
    }

    std::vector<int> pos;

    for (int i = 0; i - 1 + s.size() < size; ++i) {
        long long current_hash_M1 = (hash_sum_M1[i + s.size()] + M1 - hash_sum_M1[i]) % M1;
        long long current_hash_M2 = (hash_sum_M2[i + s.size()] + M2 - hash_sum_M2[i]) % M2;
        if (search_hash_M1 * pow_M1[i] % M1 == current_hash_M1 &&
            search_hash_M2 * pow_M2[i] % M2 == current_hash_M2) {
            pos.push_back(i);
        }
    }
    output << pos.size() << '\n';
    for (const auto &x: pos) output << x << " ";

    return 0;
}