Cod sursa(job #3363196)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:31:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
#define BAZA 113
#define MOD 1000000007
#define MAXL 2000000

using namespace std;

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

int H[MAXL + 1], B[MAXL + 1], inv[MAXL + 1];
vector <int> afis;

int putere(int a, int n){
    int t;
    if(n == 0){
        return 1;
    }
    if(n % 2 == 1){
        return (long long)putere(a, n - 1) * a % MOD;
    }
    t = putere(a, n / 2);
    return (long long)t * t % MOD;
}

int t(char ch){
    int rez;
    if('0' <= ch && ch <= '9'){
        rez = ch + 1;
    }else if('a' <= ch && ch <= 'z'){
        rez = ch - 'a' + 11;
    }else if('A' <= ch && ch <= 'Z'){
        rez = ch - 'A' + 37;
    }
    return rez;
}
int inv_mod(int x){
    return putere(x, MOD - 2);
}

int getHash(int st, int dr){
    return (((long long)(H[dr] - H[st - 1] + MOD) % MOD) * inv[st]) % MOD;
}

int main()
{
    int Hmic, p, cnt, i;
    string S1, S2;

    fin >> S1 >> S2;

    Hmic = 0;
    p = 1;
    for(i = 0; i < S1.size(); i++){
        Hmic = (Hmic + (long long)p * t(S1[i])) % MOD;
        p = ((long long)p * BAZA) % MOD;
    }

    p = 1;
    for(i = 0; i < S2.size(); i++){
        H[i] = (H[i - 1] + ((long long)p * t(S2[i]) % MOD)) % MOD;
//        printf("p = %d, H[%d] = %d\n", (long long)p * t(S2[i]) % MOD, i, H[i]);
        B[i] = p;
        p = ((long long)p * BAZA) % MOD;
    }
    inv[S2.size() - 1] = inv_mod(B[S2.size() - 1]);
    for(i = S2.size() - 2; i >= 0; i--){
        inv[i] = ((long long)BAZA * inv[i + 1]) % MOD;
//        printf("inv[%d] = %d\n", i, inv[i]);
    }

    cnt = 0;
    for(i = S1.size() - 1; i < S2.size(); i++){
//        printf("Hmic = %d, H = %d, st = %d dr = %d %d\n", Hmic, getHash(i - S1.size() + 1, i), i - S1.size() + 1, i, H[i]);
        if(getHash(i - S1.size() + 1, i) == Hmic){
            cnt++;
            if(cnt <= 1000){
                afis.push_back(i - S1.size());
            }
        }
    }
    fout << cnt << "\n";
    sort(afis.begin(), afis.end());
    for(i = 0; i < afis.size(); i++){
        fout << afis[i] + 1<< " ";
    }
    fout << "\n";
    return 0;
}