Cod sursa(job #3249729)

Utilizator Iustin_Mircea2010Iustin Mircea Iustin_Mircea2010 Data 17 octombrie 2024 16:42:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 100076969
int sp[2000005];
int op[2000005];
int ans[1005];
int find_ch(char c){
    if(c >= 'a' && c <= 'z')
        return c - 'a' + 1;
    else if(c >= 'A' && c <= 'Z')
        return c - 'A' + 27;
    else
        return c - '0' + 43;
}
int exprapid(int b, int e){
    int ans = 1;
    while(e){
        if(e & 1){
            ans *= b;
            ans %= MOD;
        }
        b *= b;
        b %= MOD;
        e >>= 1;
    }
    return ans % MOD;
}
signed main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a, b;
    cin >> a >> b;
    int start = exprapid(71, MOD - 2);
    op[0]=1;
    op[1] = start;
    for(int i = 2; i <= b.size(); i++){
        op[i] = (op[i-1] * start) % MOD;
        op[i] %= MOD;
    }
    int nr_special = 0, baza = 71;
    for(int i = 0; i < a.size(); i++){
        nr_special += (find_ch(a[i])*baza) % MOD;
        nr_special %= MOD;
        baza *= 71;
        baza %= MOD;
    }
    baza =71;
    int cntstop = 0;
    for(int i = 1; i <= b.size(); i++){
        sp[i] = (sp[i-1] + (find_ch(b[i-1])*baza)%MOD) % MOD;
        baza*=71;
        baza%=MOD;
    }
    for(int i = a.size(); i <= b.size(); i++){
        int nr_actual;
        nr_actual = sp[i] + MOD - sp[i - a.size()];
        nr_actual %= MOD;
        nr_actual *= op[i - a.size()];
        nr_actual%=MOD;
        if(nr_actual == nr_special){
            ans[cntstop++] = i - a.size();
        }
    }
    cout << cntstop << '\n';
    for(int i = 0; i < min(1LL*1000, cntstop); i++){
        cout << ans[i] << " ";
    }
    return 0;
}