Cod sursa(job #2768805)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 12 august 2021 11:33:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD = 1e9 + 7;
const int P = 52;
vector<int>value(123), ans;
int N, M, ha, hb, p = 1, cnt;
string a, b;
int main() {
    fin >> a >> b;
    N = a.size();
    M = b.size();
    if(N > M) {
        fout << "0\n";
        return 0;
    }
    for(int i = 'A'; i <= 'Z'; i++) {
        value[i] = i - 'A';
    }
    for(int i = 'a'; i <= 'z'; i++) {
        value[i] = i - 'a' + 26;
    }
    for(int i = 0; i < N; i++) {
        ha = (1LL * ha * P + value[a[i]]) % MOD;
        if(i != N - 1) {
            p = (1LL * p * P) % MOD;
        }
    }
    for(int i = 0; i < N; i++) {
        hb = (1LL * hb * P + value[b[i]]) % MOD;
    }
    if(hb == ha) {
        ans.push_back(0);
    }
//    cout << ha << '\n' << hb << "\n\n";
    for(int i = N; i < M; i++) {
        int over = (1LL * value[b[i - N]] * p) % MOD;
        hb = (hb - over + MOD) % MOD;
        hb = (1LL * hb * P) % MOD;
        hb = (hb + value[b[i]]) % MOD;
        if(hb == ha) {
            cnt++;
        }
        if(cnt <= 1000) {
            ans.push_back(i - N + 1);
        }
//        cout << hb << '\n';
    }
    fout << cnt << '\n';
    for(auto it: ans) {
        fout << it << " ";
    }
    fout << '\n';
    return 0;
}