Cod sursa(job #2763559)

Utilizator flibiaVisanu Cristian flibia Data 14 iulie 2021 22:37:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>

using namespace std;

long long power(long long base, long long exp, int MOD) {
    long long ans = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            ans = (ans * base) % MOD;
        }

        base = (base * base) % MOD;
        exp >>= 1;
    }

    return ans;
}

vector<long long> buildHash(string &s, int P, int MOD) {
    int n = s.size();
    vector<long long> sum(n, 0);

    for (int i = 0; i < n; i++) {
        if (i > 0) {
            sum[i] = sum[i - 1];
        }
        sum[i] += (power(P, i, MOD) * s[i]) % MOD;
        sum[i] %= MOD;
    }

    return sum; 
}

long long getHash(vector<long long> &sum, int P, int MOD, int l, int r) {
    long long ans = sum[r] - (l > 0 ? sum[l - 1] : 0);
    ans = (ans % MOD + MOD) % MOD;
    ans = (ans * power(power(P, l, MOD), MOD - 2, MOD)) % MOD;

    return ans;
}

int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    
    string a[2];
    cin >> a[0] >> a[1];

    int MOD[2] = {1000000007, 1000000033};
    int P[2] = {57, 61};

    vector<int> id;

    vector<long long> hashes[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            hashes[i][j] = buildHash(a[i], P[j], MOD[j]);
        }
    }

    int l = a[0].size();
    for (int i = 0; i + l - 1 < a[1].size(); i++) {
        int f = 1;
        for (int j = 0; j < 2; j++) {
            if (getHash(hashes[0][j], P[j], MOD[j], 0, l - 1) != getHash(hashes[1][j], P[j], MOD[j], i, i + l - 1)) {
                f = 0;
                break;
            }
        }

        if (f) {
            id.push_back(i);
        }
    }
    
    cout << id.size() << '\n';
    for (int i = 0; i < min(1000, (int) id.size()); i++) {
        cout << id[i] << ' ';
    }

    return 0;
}