Cod sursa(job #3142377)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 21 iulie 2023 00:09:26
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 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;

    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;
        if (power_p[i] < 0) power_p[i] += MOD;
    }

    for (int i = 0; i < n; i++) {
        if(i > 0)
            hash_prefixes[i] = (hash_prefixes[i - 1] + ((T[i] - 'a' + 1) * power_p[i]) % MOD) % MOD;
        else
            hash_prefixes[i] = ((T[i] - 'a' + 1) * power_p[i]) % MOD;
        if (hash_prefixes[i] < 0) hash_prefixes[i] += 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;
        if (hash_P < 0) hash_P += MOD;
    }

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

        if (hash_substring < 0) hash_substring += MOD;
        if (hash_pattern < 0) hash_pattern += MOD;

        if (hash_substring == hash_pattern) {
            cnt++;
            if (ans.size() < 1000) {
                ans.pb(i);
            }
        }
    }

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

    return 0;
}