Cod sursa(job #2976989)

Utilizator rares89_Dumitriu Rares rares89_ Data 10 februarie 2023 15:55:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
// sursa cu rabin-karp
#include <fstream>
#include <climits>
#include <cstring>
#include <vector>
#define d 73 // baza

using namespace std;

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

char a[2000005], b[2000005];
vector<int> ans;

int main() {
    fin >> a >> b;
    if(a > b) {
        fout << "0";
        return 0;
    }
    int MOD = INT_MAX;
    int m = strlen(a), n = strlen(b);
    int hA = 0, hB = 0; // hash-ul pt a, respectiv hash-ul pt b
    int h = 1;
    
    for(int i = 0; i < m - 1; i++) {
        h = (h * d) % MOD;
    }
    for(int i = 0; i < m; i++) {
        hA = (d * hA + a[i]) % MOD;
        hB = (d * hB + b[i]) % MOD;
    }
    for(int i = 0; i <= n - m; i++) {
        if(hA == hB) {
            int j;
            for(j = 0; j < m; j++) {
                if(b[i + j] != a[j]) {
                    break;
                }
            }
            if(j == m) {
                ans.push_back(i);
                if(ans.size() == 1000) {
                    break;
                }
            }
        }
        if(i < n - m) {
            hB = (d * (hB - b[i] * h) + b[i + m]) % MOD;
            if(hB < 0) {
                hB = (hB + MOD);
            }
        }
    }
    fout << ans.size() << "\n";
    for(auto i : ans) {
        fout << i << " ";
    }
    return 0;
}