Cod sursa(job #2977188)

Utilizator rares89_Dumitriu Rares rares89_ Data 11 februarie 2023 00:36:49
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
// sursa cu rabin-karp
#include <fstream>
#include <cstring>
#include <vector>
#define MOD1 66601
#define MOD2 66701

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 n = strlen(a), m = strlen(b);
    int hA1 = 0, hA2 = 0, hB1 = 0, hB2 = 0; // hash-uri pt a, respectiv hash-uri pt b
    int h1 = 1, h2 = 1;
    for(int i = 0; i < n; i++) {
        hA1 = (26 * hA1 + a[i]) % MOD1;
        hA2 = (26 * hA2 + a[i]) % MOD2;
        hB1 = (26 * hB1 + b[i]) % MOD1;
        hB2 = (26 * hB2 + b[i]) % MOD2;
        if(i != 0) {
            h1 = (h1 * 26) % MOD1;
            h2 = (h2 * 26) % MOD2;
        }
    }
    if(hA1 == hB1 && hA2 == hB2) {
        ans.push_back(0);
    }
    for(int i = n; i < m; i++) {
        hB1 = ((hB1 - (b[i - n] * h1) % MOD1 + MOD1) * 26 + b[i]) % MOD1;
        hB2 = ((hB2 - (b[i - n] * h2) % MOD2 + MOD2) * 26 + b[i]) % MOD2;
        if(hA1 == hB1 && hA2 == hB2) {
            ans.push_back(i - n + 1);
            if(ans.size() == 1000) {
                break;
            }
        }
    }
    fout << ans.size() << "\n";
    for(auto i : ans) {
        fout << i << " ";
    }
    return 0;
}