Cod sursa(job #3142375)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 20 iulie 2023 23:59:36
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

ll MOD = 1e9 + 7;
ll p = 53;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string P, T;
    f >> P >> T;

    T = " " + T;
    int n = T.size();
    vector<ll> hash_prefixes(n, 0), power_p(n, 1);
    for (int i = 1; i < n; i++)
        power_p[i] = (power_p[i - 1] * p) % MOD;

    for (int i = 1; i < n; i++) {
        hash_prefixes[i] = (hash_prefixes[i - 1] + ((T[i] - 'a' + 1) * power_p[i]) % MOD) % MOD;
    }

    int hash_P = 0;
    for (int i = 0; i < P.size(); i++) {
        hash_P = (hash_P + ((P[i] - 'a' + 1) * power_p[i]) % MOD) % MOD;
    }

    int cnt = 0;
    vector<int> ans;
    for (int i = 1; i < n - P.size(); i++) {
        int j = i + P.size() - 1;
        int hash_substring = (hash_prefixes[j] - hash_prefixes[i - 1] + MOD) % MOD; // +MOD to avoid negative numbers
 
        if (hash_substring == (MOD + (hash_P * power_p[i]) % MOD) % MOD) {
            cnt++;
            if (ans.size() < 1000) {
                ans.pb(i - 1);
            }
        }
    }

    g << cnt << '\n';
    for (int x : ans) g << x << ' ';

    return 0;
}