Cod sursa(job #3171109)

Utilizator Cyrex.1948Dumitrica Cezar Stefan Cyrex.1948 Data 18 noiembrie 2023 13:13:40
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <vector>
#include <string>

const int MOD1 = 666013;
const int BASE1 = 101;
const int BASE2 = 103;
const int MOD2 = 666019;

int cnt;
std::vector<int> rez;

void HashFunc(const std::string& pattern, const std::string& str) {
    int M = pattern.size();
    int N = str.size();
    int pattern_hash1 = 0;
    int pattern_hash2 = 0;
    int str_hash1 = 0;
    int str_hash2 = 0;
    int power = 1;

    for (int i = 0; i < M - 1; i++)
        power = (power * BASE1) % MOD1;

    for (int i = 0, j = 0; i < M; i++) {
        pattern_hash1 = (BASE1 * pattern_hash1 + pattern[i]) % MOD1;
        pattern_hash2 = (BASE2 * pattern_hash2 + pattern[i]) % MOD2;
        str_hash1 = (BASE1 * str_hash1 + str[i]) % MOD1;
        str_hash2 = (BASE2 * str_hash2 + str[i]) % MOD2;
    }

    for (int i = 0, j = 0; i <= N - M; ++i) {
        if (pattern_hash1 == str_hash1 && pattern_hash2 == str_hash2) {
            if (j == M) {
                if (rez.size() < 1000) {
                    rez.push_back(i);
                }
                cnt++;
            }
        }

        if (i < N - M) {
            str_hash1 = (BASE1 * (str_hash1 - str[i] * power) + str[i + M]) % MOD1;
            str_hash2 = (BASE2 * (str_hash2 - str[i] * power) + str[i + M]) % MOD2;

            if (str_hash1 < 0)
                str_hash1 += MOD1;

            if (str_hash2 < 0)
                str_hash2 += MOD2;
        }
        j++;
    }
}

int main() {
    std::string pattern, str;
    std::cin >> pattern >> str;
    HashFunc(pattern, str);
    std::cout << cnt << '\n';

    for (int i = 0; i < rez.size(); i++) {
        std::cout << rez[i] << ' ';
    }

    return 0;
}