Cod sursa(job #2763563)

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

using namespace std;

const int N = 2e6 + 10;

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

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;
}

void build(int lim) {
    for (int i = 0; i < 2; i++) {
        pw[i][0] = 1;
        inv[i][0] = 1;
    }
    int aux[2] = {power(P[0], MOD[0] - 2, MOD[0]), power(P[1], MOD[1] - 2, MOD[1])};

    for (int i = 0; i < 2; i++) {
        for (int j = 1; j < lim; j++) {
            pw[i][j] = (1ll * pw[i][j - 1] * P[i]) % MOD[i];
            inv[i][j] = (1ll * inv[i][j - 1] * aux[i]) % MOD[i];
        }
    }
}

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

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

    return sum; 
}

int getHash(vector<int> &sum, int id, int l, int r) {
    int ans = sum[r] - (l > 0 ? sum[l - 1] : 0);
    ans = (ans % MOD[id] + MOD[id]) % MOD[id];
    ans = (1ll *ans * inv[id][l]) % MOD[id];

    return ans;
}

int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    
    build(2e6);

    string a[2];
    cin >> a[0] >> a[1];

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

    vector<int> id;
    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], j, 0, l - 1) != getHash(hashes[1][j], 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;
}