Cod sursa(job #3231352)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 25 mai 2024 22:10:08
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;
#define unsigned long long int
const int mod = 2000000011, p = 53, N = 2e6 + 5;

string a, b;
int hash1[N], hash2[N], n, m;

int pw(int a, int n) {
    if (!n)
        return 1;
    else {
        if (n % 2)
            return a * pw(a, n - 1) % mod;
        else {
            int c = pw(a, n / 2);
            return c * c % mod;
        }
    }
}

int cod(char c) {
    if (islower(c)) {
        return c - 'a' + 1;
    } else {
        return c - 'A' + 27;
    }
}

int get_hash(int l, int r) {
    return ((hash2[r] - hash2[l - 1] + mod) % mod) * pw(pw(p, l), mod - 2) % mod;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> a >> b;
    n = a.size(); m = b.size();
    hash1[0] = cod(a[0]);
    for (int i = 1; i < n; i++) {
        hash1[i] = (cod(a[i]) * pw(p, i) % mod);
        hash1[i] = (hash1[i - 1] + hash1[i]) % mod;
    }
    int hash_value_1 = hash1[n - 1];
    hash2[0] = cod(b[0]);
    for (int i = 1; i < m; i++) {
        hash2[i] = (hash2[i - 1] + (cod(b[i])) * pw(p, i) % mod) % mod;
    }
    vector<int> ans;
    int cnt = 0;
    for (int i = 0; i < m - n + 1; i++) {
        if (i > 0 && get_hash(i, i + n - 1) == hash_value_1) {
            cnt++;
            ans.emplace_back(i);
        }
        else if (i == 0 && hash2[n - 1] == hash_value_1) {
            cnt++;
            ans.emplace_back(i);
        }
    }
    cout << cnt << '\n';
    for (auto it : ans)
        cout << it << ' ';
    return 0;
}