Cod sursa(job #2910359)

Utilizator Frant_IoanaFrant Ioana Frant_Ioana Data 19 iunie 2022 20:35:08
Problema Potrivirea sirurilor Scor 74
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b;
const int p = 53;
const int m = 1e9 + 9;

int main(){
    fin >> a >> b;
    int A = a.size(), B = b.size();

    vector<long long> p_pow(max(A, B) + 1);
    p_pow[0] = 1;
    for(int i = 1; i < (int) p_pow.size(); i++)
        p_pow[i] = (p_pow[i - 1] * p) % m;
    
    vector<long long> h(B + 1, 0);
    for(int i = 0; i < B; i++)
        h[i + 1] = (h[i] + (b[i] - 'A' + 1) * p_pow[i]) % m;
    
    long long h_a = 0;
    for(int i = 0; i < A; i++)
        h_a = (h_a + (a[i] - 'A' + 1) * p_pow[i]) % m;
    
    vector<int> occurences;
    for(int i = 0; i + A - 1 < B; i++){
        long long cur_h = (h[i + A] + m - h[i]) % m;
        if(cur_h == h_a * p_pow[i] % m)
            occurences.push_back(i);
    }

    fout << occurences.size() << '\n';
    for(int i = 0; i < min(1000, (int) occurences.size()); i++)
        fout << occurences[i] << ' ';
}